Point Location in 3D Subdivision
Given a three-dimensional subdivision with faces, is there a data structure using space that answers point-location queries in time? Here a query asks for the face containing a queried point. The question does not specify restrictions on the faces, a computational model, or conventions for points on boundaries; no such restrictions are imposed in this formulation.
Background
The question appeared in Mitchell and O’Rourke’s 2001 computational geometry column; the problem entry gives its origin as uncertain. A result cited as a baseline is Snoeyink’s 1997 handbook account, which gives an -space structure with query time for the stated three-dimensional subdivision problem. TOPP, Problem 13 Mitchell and O’Rourke (2001)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.