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