The report FIMU-RS-99-07
Linear BSP Tree in the Plane for Set of Segments with Low Directional Density
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.
Please install a newer browser for this site to function properly.