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.
- 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 - July 24, 2008