The Open Problems Project

Next: Problem 14: Binary Space Partition Size

Previous: Problem 12: Dynamic Planar Convex Hull

Problem 13: Point Location in 3D Subdivision

Statement

Is there an O(n)-space data structure that supports O(\log n)-time point-location queries in a three-dimensional subdivision of n faces?

Origin

Uncertain, pending investigation.

Status/Conjectures

Open.

Partial and Related Results

Currently O(n \log n) space and O(\log^2 n) queries are achievable [Sno97].

Appearances

[MO01]

Categories

data structures

Entry Revision History

J. O’Rourke, 2 Aug. 2001.

Bibliography

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

[Sno97]

Jack Snoeyink. Point location. In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 30, pages 559–574. CRC Press LLC, Boca Raton, FL, 1997.