next up previous
Next: Problem 14: Binary Space Up: The Open Problems Project Previous: Problem 12: Dynamic Planar


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(log2n) 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.



The Open Problems Project - December 04, 2015