Abstract
In this paper we prove the existence of binary space partitions (BSPs) with linear size for sets of axis-parallel boxes in three dimensional space under certain conditions that are often satisfied in practical situations. In particular, we give an O(n log n) time algorithm to construct a BSP tree with linear size for a set S of axis-parallel boxes where the ratio between the lengths of the longest and the shortest edges of boxes in S is bounded by a constant. The BSP tree constructed is balanced if S has a constant profile.
In view of the lower bound of Ω(n3/2) for the size of BSPs for set of n line segments (or boxes) in ℝ3, this is the first class of high dimensional objects that are found, for which linear size BSPs exist. We generalize the results for sets of hyperrectangles in dimension greater than three and extend our method also for a useful class of d-dimensional fat objects. All the algorithms for constructing linear size binary space partitions presented in this paper are simple enough to be favorable for implementations.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Chazelle. Filtering search: a new approach to query-answering. SIAM J. Comput., 15:703–724, 1986.
F. d'Amore and P. G. Franciosa. On the optimal binary plane partition for sets of isothetic rectangles. Inform. Process. Lett., 44:255–259, 1992.
M. de Berg. Linear size binary space partitions for fat objects. To appear, Dept. of Computer Science, Utrecht University, the Netherlands, 1995. (accepted for Euro. Symp. on Algorithms, ESA'95).
M. de Berg and M. de Groot. Binary space partitions for sets of cubes. In Abstracts 10th European Workshop Comput. Geom. (CG'94), pages 84–88, 1994.
M. de Berg, M. de Groot, and M. Overmars. New results on binary space partitions in the plane. In Proc. 4th Scand. Workshop Algorithm Theory, volume 824 of Lecture Notes in Computer Science, pages 61–72, 1994.
H. Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, West Germany, 1987.
J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, and Phillips. Introduction to Computer Graphics. Addison-Wesley, Reading, MA, 1993.
H. Fuchs, Z. M. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. Comput. Graph., 14(3):124–133, 1980.
E. M. McCreight. Priority search trees. SIAM J. Comput., 14:257–276, 1985.
B. Naylor, J. A. Amatodes, and W. Thibault. Merging BSP trees yields polyhedral set operations. Comput. Graph., 24(4):115–124, August 1990.
V. H. Nguyen, T. Roos, and P. Widmayer. Balanced cuts of a set of hyperrectangles. In Proc. 5th Canad. Conf. Comput Geom., pages 121–126, Waterloo, Canada, 1993.
J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. on Database Systems, 9:38–71, 1984.
M. S. Paterson and F. F. Yao. Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom., 5:485–503, 1990.
M. S. Paterson and F. F. Yao. Optimal binary space partitions for orthogonal objects. J. Algorithms, 13:99–113, 1992.
H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, 1990.
R. A. Schumaker, R. Brand, M. Gilliland, and W. Sharp. Study for applying computer-generated images to visual simulation. Report AFHRL-TR-69-14, U.S. Air Force Human Resources Lab., 1969. cited in [8].
I. E. Sutherland, R. F. Sproull, and R. A. Schumaker. A characterization of ten hidden surface algorithms. ACM Comput. Surv., 6:1–55, 1974. cited in [8].
S. Teller and P. Hanrahan. Global visibility algorithms for illumination computations. In Proc. SIGGRAPH '93, pages 239–246, 1993.
W. C. Thibault and B. F. Naylor. Set operations on polyhedra using binary space partitioning trees. In Proc. SIGGRAPH'87, pages 153–162, 1987.
A. F. van der Stappen, D. Halperin, and M. H. Overmars. The complexity of the free space for a robot moving amidst fat obstacles. Comput. Geom. Theory and Appl., 3:353–373, 1993.
P. van Oosterom. A modified binary space partition for geographic information systems. Int. J. GIS, 4(2):133–146, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, V.H., Widmayer, P. (1995). Binary space partitions for sets of hyperrectangles. In: Kanchanasut, K., Lévy, JJ. (eds) Algorithms, Concurrency and Knowledge. ACSC 1995. Lecture Notes in Computer Science, vol 1023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60688-2_35
Download citation
DOI: https://doi.org/10.1007/3-540-60688-2_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60688-8
Online ISBN: 978-3-540-49262-7
eBook Packages: Springer Book Archive