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 Ω(n4/3) and O(nα log2n), 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 Θ(n3/2). We also show that the worstcase complexity of a BSP for a general convex polyhedral subdivision of total complexity O(n) is Ω(n3/2).
展开▼
机译：我们考虑以下问题：如果将空间细分为 n 个凸多面体单元，则该细分空间的二进制空间分区（BSP）的最坏情况复杂度是多少？我们表明，如果细分为矩形且与轴对齐，则轴对齐的BSP的最坏情况复杂度为Ω（ n 4/3 ）和 O （ n α log 2 n ），其中α= 1 + log 2 （4/3）= 1.4150375 ....相比之下，众所周知，未形成细分的 n 个矩形单元的集合的BSP具有最坏情况的复杂度Θ（ n 3/2 ）。我们还表明，总复杂度 O （ n ）的一般凸多面体细分的BSP的最坏情况复杂度为Ω（ n 3/2 ）。
展开▼
