Better Late than Never: the Complexity of Arrangements of Polyhedra

Abstract

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.

An earlier version appeared in EuroCG 2025