by Petr Tobola, Karel Nechvíle, April 2003, 21 pages.
FIMU-RS-2003-02. Available as Postscript, PDF.
We consider the problem of constructing binary space partitions for the
by Petr Tobola, Karel Nechvíle, September 2000, 27 pages.
FIMU-RS-2000-04. Available as Postscript, PDF.
We consider the problem of constructing of binary space partitions (BSP) for a set S of n hyperrectangles in arbitrary dimensional space. If the set S fulfills the low directional density condition defined in this paper then the resultant BSP has O(n) size and it can be constructed in O(n log^2 n) time in R^3. The low directional density condition defines a new class of objects which we are able to construct a linear BSP for. The method is quite simple and it should be appropriate for practical implementation.
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.