Complexity of vertical decompositions in five and more dimensions
The question concerns the worst-case combinatorial complexity of the vertical decomposition of the arrangement of $n$ surfaces in $\mathbb{R}^d$.
The lower bound is $\Omega(n^d)$. Upper bounds nearly matching it were known up to $d = 3$, as surveyed by Agarwal and Sharir, with a gap from $d = 4$ on. Koltun obtained an almost tight bound for $d = 4$ and an upper bound of $O(n^{2d-4+\varepsilon})$, for every $\varepsilon > 0$, in every dimension $d$, so the bounds still differ when $d \ge 5$.
Problem. For $d \ge 5$, determine the combinatorial complexity of the vertical decomposition of an arrangement of $n$ surfaces in $\mathbb{R}^d$.
Source: Origin uncertain; Problem 19 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- arrangements of surfaces, The Open Problems Project, vertical decomposition
References
@incollection{agarwalsharir2000,
author = {Agarwal, Pankaj K. and Sharir, Micha},
title = {{Davenport--Schinzel} sequences and their geometric applications},
editor = {Sack, J{\"o}rg-R{\"u}diger and Urrutia, Jorge},
booktitle = {Handbook of Computational Geometry},
publisher = {Elsevier Publishers B.V. North-Holland},
address = {Amsterdam},
year = {2000},
pages = {1--47},
}
@inproceedings{koltun2001,
author = {Koltun, Vladlen},
title = {Almost tight upper bounds for vertical decompositions in four dimensions},
booktitle = {Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci.},
year = {2001},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01075, "Complexity of vertical decompositions in five and more dimensions", clopen.solutions.