We introduce a new BSP tree construction method for set of segments in the plane. Our algorithm is able to create BSP tree of linear size in the time $O(n \log^3 n)$ for set of segments with low directional density (i.e. it holds for arbitrary segment $s_i$ from such set, that a line created as extension of this segment doesn't intersect too many other segments from the set in a near neighbourhood of $s_i$) and a directional constant $\delta$ belonging to this set.

Hosted by Graphics & Media Lab. http://graphics.cs.msu.su

mailto: Webmaster