Binary space partitions for 3D subdivisions

ABSTRACT

We consider the following question: Given a subdivision of space into n convex polyhedral cells, what is the worst-case complexity of a binary space partition (BSP) for the subdivision? We show that if the subdivision is rectangular and axis-aligned, then the worstcase complexity of an axis-aligned BSP is Ω(n^4/3) and O(n^α log² n), where α = 1 + log2(4/3 ) = 1.4150375 .... By contrast, it is known that the BSP of a collection of n rectangular cells not forming a subdivision has worstcase complexity Θ(n^3/2). We also show that the worstcase complexity of a BSP for a general convex polyhedral subdivision of total complexity O(n) is Ω(n^3/2).

REFERENCES

• 1: C. Ballieux. Motion planning using binary space partitions. Technical Report Inf/src/93--25, Utrecht University, 1993.
• 2: Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan, Slice and dice: a simple, improved approximate tiling recipe, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.455-464, January 06-08, 2002, San Francisco, California
• 3: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 4: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.99-106, July 1989
• 5: Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147159]
• 6: 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]
• 7: Adrian Dumitrescu , Joseph S. G. Mitchell , Micha Sharir, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Proceedings of the seventeenth annual symposium on Computational geometry, p.141-150, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378649]
• 8: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 9: Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.115-124, Aug. 1990
• 10: B. Naylor and W. Thibault. Application of BSP trees to ray-tracing and CSG evaluation. Technical Report GIT-ICS 86/03, Georgia Institute of Tech., School of Information and Computer Science, February 1986.
• 11: 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]
• 12: 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]
• 13: R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp. Study for applying computer-generated images to visual simulation. Technical Report AFHRL-TR-69--14, U.S. Air Force Human Resources Laboratory, 1969.
• 14: 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
• 15: Csaba D. Tóth, Binary space partitions for line segments with a limited number of directions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.465-471, January 06-08, 2002, San Francisco, California
• 16: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory