Binary space partitions for 3D subdivisions
John E. Hershberger, Subhash Suri · 2003
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 ) and O(n n), where # = 1+log 2 (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 ). We also show that the worstcase complexity of a BSP for a general convex polyhedral subdivision of total complexity O(n) is #(n ).