**Next:** Problem 20: Minimum Stabbing Spanning Tree

**Previous:** Problem 18: Pushing Disks Together

- Statement
What is the complexity of the

*vertical decomposition*of n surfaces in \R^d, d \ge 5?- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- 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.

- Appearances
- Categories
combinatorial geometry

- Entry Revision History
J. O’Rourke, 2 Aug. 2001.

- [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.