Technical Reports
The report FIMU-RS-99-07
Linear BSP Tree in the Plane for Set of Segments with Low Directional Density
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.
Abstract:
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.
Responsible contact:
vedaXDjbU2LSW@fiQ1T5fpnNE.muni8CVI=SRv5.cz
Please install a newer browser for this site to function properly.