The Open Problems Project

Next: Problem 20: Minimum Stabbing Spanning Tree

Previous: Problem 18: Pushing Disks Together

Problem 19: Vertical Decompositions in \R^d


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


Uncertain, pending investigation.



Partial and Related Results

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

Entry Revision History

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.