Linear BSP Trees for Sets of Hyperrectangles with Low Directional Density

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

TOBOLA Petr NECHVÍLE Karel

Year of publication 2001
Type Article in Proceedings
Conference WSCG' 2001, Conference proceedings
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Keywords BSP; partitioning; hyperrectangle
Description We consider the problem of constructing of binary space partitions (BSP) for a set S of n hyperrectangles in space with constant dimension. 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 effectively. 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.