by Petr Tobola, Karel Nechvíle, A full version of the paper which appeared in Proceedings WSCG`99. September 1999, 20 pages.
FIMU-RS-99-07. Available as Postscript, PDF.
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.