Next: Problem 20: Minimum Stabbing
Up: The Open Problems Project
Previous: Problem 18: Pushing Disks
Problem 19: Vertical Decompositions in
^{d}
 Statement
 What is the complexity of the vertical decomposition
of n surfaces in
^{d}, d≥5?
 Origin
 Uncertain, pending investigation.
 Status/Conjectures
 Open.
 Partial and Related Results
 The lower bound of
Ω(n^{d}) was nearly
achieved up to d = 3 [AS00a, p. 271],
but a gap remained for d≥4.
A recent result [Kol01]
covers d = 4 and achieves
O(n^{2d4+ε}) for general d,
leaving a gap for d≥5.
 Appearances
 [MO01]
 Categories
 combinatorial geometry
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001.
 AS00a

Pankaj K. Agarwal and Micha Sharir.
DavenportSchinzel sequences and their geometric applications.
In JörgRüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 147. Elsevier Publishers B.V.
NorthHolland, 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):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
The Open Problems Project  September 19, 2017