next up previous
Next: Problem 20: Minimum Stabbing Up: The Open Problems Project Previous: Problem 18: Pushing Disks


Problem 19: Vertical Decompositions in $ \mathbb {R}$d

Statement
What is the complexity of the vertical decomposition of n surfaces in $ \mathbb {R}$d, d≥5?
Origin
Uncertain, pending investigation.
Status/Conjectures
Open.
Partial and Related Results
The lower bound of Ω(nd) was nearly achieved up to d = 3 [AS00a, p. 271], but a gap remained for d≥4. A recent result [Kol01] covers d = 4 and achieves O(n2d-4+ε) for general d, leaving a gap for d≥5.
Appearances
[MO01]
Categories
combinatorial geometry
Entry Revision History
J. O'Rourke, 2 Aug. 2001.

Bibliography

AS00a
Pankaj K. Agarwal and Micha Sharir.
Davenport-Schinzel sequences and their geometric applications.
In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 1-47. Elsevier Publishers B.V. North-Holland, Amsterdam, 2000.

Kol01
Vladlen Koltun.
Almost tight upper bounds for vertical decompositions in four dimensions.
In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., 2001.

MO01
J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.



The Open Problems Project - December 04, 2015