Vertical Decompositions in R^d

For fixed $d\geq5$ and fixed $\varepsilon>0$ , let $\mathcal{A}$ be an arrangement of $n$ constant-complexity algebraic surface patches in $\mathbb{R}^d$ . Determine the tight worst-case number of cells in the vertical decomposition of $\mathcal{A}$ , in particular whether a bound near $O(n^d)$ holds.

Download

Abstract

Determine the worst-case combinatorial complexity of the vertical decomposition of an arrangement of $n$ constant-complexity surfaces in $\mathbb{R}^d$ for $d\geq5$ .

Background and progress

The known lower bound is $\Omega(n^d)$ , and essentially matching bounds are known through dimension three [Agarwal and Sharir, 2000]. Koltun obtained an $O(n^{2d-4+\varepsilon})$ upper bound and covered dimension four [Koltun, 2001]; the higher-dimensional gap remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p19.

Reference papers

Arrangements and their applicationsPankaj K. Agarwal, Micha SharirHandbook of Computational Geometry · 2000
Almost tight upper bounds for vertical decompositions in four dimensionsVladlen KoltunProceedings of the 42nd IEEE Symposium on Foundations of Computer Science · 2001