Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles

ABSTRACT

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of the analysis in \cite{dAF} is that any set of $n$ axis-parallel and pairwise-disjoint line segments in the plane admits a binary space partition of size at most $2n-1$. We establish a worst-case lower bound of $2n-o(n)$ for the size of such a BSP, thus showing that this bound is almost tight in the worst case. (b) We give an improved worst-case lower bound of $\frac{9}{4}n-o(n)$ on the size of a BSP for isothetic pairwise disjoint rectangles. (c) We present simple methods, with equally simple analysis, for constructing BSP's for axis-parallel segments in higher dimensions, simplifying the technique of \cite{PY2} and improving the constants. (d) We obtain an alternative construction (to that in \cite{PY2}) of BSP's for collections of axis-parallel rectangles in 3-space. (e) We present a construction of BSP's of size $O(n^{5/3})$ for $n$ axis-parallel pairwise disjoint 2-rectangles in $\reals^4$, and give a matching worst-case lower bound of $\Omega(n^{5/3})$ for the size of such a BSP. (f) We extend the results of \cite{PY2} to axis-parallel $k$-dimensional rectangles in $\reals^d$, for $k

REFERENCES

• 1: Fabrizio d'Amore , Paolo Guilio Franciosa, On the optimal binary plane partition for sets of isothetic rectangles, Information Processing Letters, v.44 n.5, p.255-259, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90210-M]
• 2: Mark de Berg , Marko de Groot , Mark Overmars, New results on binary space partitions in the plane, Computational Geometry: Theory and Applications, v.8 n.6, p.317-333, Nov. 1997 [doi>10.1016/S0925-7721(97)00008-4]
• 3: Mark de Berg , Marko M. de Groot , Mark H. Overmars, Perfect binary space partitions, Computational Geometry: Theory and Applications, v.7 n.1-2, p.81-91, Jan. 1997 [doi>10.1016/0925-7721(95)00045-3]
• 4: Berman Piotr , DasGupta Bhaskar , Muthukrishnan S., On the Exact Size of the Binary Space Partitioning of Sets of Isothetic Rectangles with Applications, Certer for Discrete Mathematics & Theoretical Computer Science, 2000
• 5: Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan , Suneeta Ramaswami, Improved approximation algorithms for rectangle tiling and packing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.427-436, January 07-09, 2001, Washington, D.C., United States
• 6: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989
• 7: S.E. Dorwald, A survey of object-space hidden surface removal, Intern. J. Comput. Geom. Appl. 4 (1994), 325-362.
• 8: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 9: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Journal of Algorithms, v.13 n.1, p.99-113, March 1992 [doi>10.1016/0196-6774(92)90007-Y]
• 10: Csaba D. T'oth, A note on binary plane partitions, Proceedings of the seventeenth annual symposium on Computational geometry, p.151-156, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378652]
• 11: C. D. Toth, BSP for line segments with a limited number of directions, Manuscript, ETH Zurich, March, 2001.
• 12: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory, Verification