The Open Problems Project

Next: Problem 20: Minimum Stabbing Spanning Tree

Previous: Problem 18: Pushing Disks Together

Problem 19: Vertical Decompositions in \R^d

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

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