The report FIMU-RS-2003-02
Linear Binary Space Partitions and Hierarchy of Object Classes
April 2003, 21 pages.
Available as Postscript,
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.