OP-01072 Open

Point location in three-dimensional subdivisions

Consider a subdivision of three-dimensional space with $n$ faces, to be preprocessed into a data structure that reports, for a query point, the cell of the subdivision containing it.

As recorded in Snoeyink's survey of point location, one can achieve $O(n\log n)$ space with $O(\log^2 n)$ query time.

Problem. For a subdivision of three-dimensional space with $n$ faces, is there a data structure of size $O(n)$ that answers point-location queries in $O(\log n)$ time?

Source: Origin uncertain; Problem 13 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary: MG — Metric Geometry
Secondary: CO
Keywords: point location, spatial subdivisions, The Open Problems Project

References

@incollection{snoeyink1997,
  author    = {Snoeyink, Jack},
  title     = {Point location},
  chapter   = {30},
  editor    = {Goodman, Jacob E. and O'Rourke, Joseph},
  booktitle = {Handbook of Discrete and Computational Geometry},
  publisher = {CRC Press LLC},
  address   = {Boca Raton, FL},
  year      = {1997},
  pages     = {559--574},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01072, "Point location in three-dimensional subdivisions", clopen.solutions.