A List by Author: Karel Nechvíle
- home page:
Linear Binary Space Partitions and Hierarchy of Object Classes
We consider the problem of constructing binary space partitions for the
Linear BSP Trees for Sets of Hyperrectangles with Low Directional Density
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
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.