Technical Reports

The report FIMU-RS-2000-04

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.