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 pointlocation queries
in a threedimensional 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.
 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.
 Sno97

Jack Snoeyink.
Point location.
In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of
Discrete and Computational Geometry, chapter 30, pages 559574. CRC Press
LLC, Boca Raton, FL, 1997.
The Open Problems Project  September 19, 2017