Vertical Decompositions in R^d

What is the complexity of the vertical decomposition of $n$ surfaces in $\mathbb{R}^d$ , $d \ge 5$ ?

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

Vertical Decompositions in R^d

Coming soon

Organizer