← All problems

Point Location in 3D Subdivision

24 years old · documented by

Given a three-dimensional subdivision with nn faces, is there a data structure using O(n)O(n) space that answers point-location queries in O(log⁡n)O(\log n) 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.

Space=O(n),query time=O(log⁡n).\text{Space}=O(n),\qquad \text{query time}=O(\log n).

TOPP, Problem 13

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 O(nlog⁡n)O(n\log n)-space structure with O(log⁡2n)O(\log^2 n) query time for the stated three-dimensional subdivision problem. TOPP, Problem 13 Mitchell and O’Rourke (2001)

References

Progress summary

Never refreshed

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.