Better Late than Never: the Complexity of Arrangements of Polyhedra
By: Boris Aronov , Sang Won Bae , Sergio Cabello and more
Potential Business Impact:
Maps spaces using shapes to count complexity.
Let $\mathcal{A}$ be the subdivision of $\mathbb{R}^d$ induced by $m$ convex polyhedra having $n$ facets in total. We prove that $\mathcal{A}$ has combinatorial complexity $O(m^{\lceil d/2 \rceil} n^{\lfloor d/2 \rfloor})$ and that this bound is tight. The bound is mentioned several times in the literature, but no proof for arbitrary dimension has been published before.
Similar Papers
On the Vertices of Delta-modular Polyhedra
Combinatorics
Helps computers count shapes faster.
The Complexity of One or Many Faces in the Overlay of Many Arrangements
Computational Geometry
Helps draw complex shapes faster on computers.
Approximation Depth of Convex Polytopes
Metric Geometry
Makes shapes simpler for computers to understand.