Next: Problem 20: Minimum Stabbing Spanning Tree
Previous: Problem 18: Pushing Disks Together
What is the complexity of the vertical decomposition of n surfaces in \R^d, d \ge 5?
Uncertain, pending investigation.
Open.
The lower bound of \Omega(n^d) was nearly achieved up to d=3 [AS00a], p. 271, but a gap remained for d \ge 4. A recent result [Kol01] covers d=4 and achieves O(n^{2d-4+\epsilon}) for general d, leaving a gap for d \ge 5.
combinatorial geometry
J. O’Rourke, 2 Aug. 2001.
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.
Vladlen Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., 2001.
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.