Technical Reports

A List by Author: Petr Tobola

e-mail:

ptx(a)fi.muni.cz

home page:

https://www.fi.muni.cz/~ptx/

Linear Binary Space Partitions and Hierarchy of Object Classes

by Petr Tobola, Karel Nechvíle, April 2003, 21 pages.

FIMU-RS-2003-02. Available as Postscript, PDF.

Abstract:

We consider the problem of constructing binary space partitions for the set P of d-dimensional objects in d-dimensional space. There are several classes of objects defined for such settings, which support design of effective algorithms. We extend the existing the de Berg hierarchy of classes by the definition of new classes derived from that one and we show desirability of such an extension. Moreover we propose a new algorithm, which works on generalized lambda-low density scenes (defined in this paper) and provides BSP tree of linear size. The tree can be constructed in O(n log^2 n) time and space, where n is the number of objects. Moreover, we can trade-off between size and balance of the BSP tree fairly simply.

Linear BSP Trees for Sets of Hyperrectangles with Low Directional Density

by Petr Tobola, Karel Nechvíle, September 2000, 27 pages.

FIMU-RS-2000-04. Available as Postscript, PDF.

Abstract:

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.

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.