Linear Binary Space Partitions and the Hierarchy of Object Classes
Petr Tobola, Karel Nechvíle · 2003
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 [8] 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 λ-low density scenes [20] (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.