Point Location in 3D Subdivision

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?

Download

Abstract

The open problem is to construct a linear-space data structure for point location in a three-dimensional subdivision that answers every query in logarithmic time. For a subdivision with $n$ faces, the reported known result uses $O(n\log n)$ space and answers queries in $O(\log^2 n)$ time.

Background and progress

The origin of the problem is uncertain. For a three-dimensional subdivision with $n$ faces, a data structure using $O(n\log n)$ space and supporting $O(\log^2 n)$ -time point-location queries is known [Snoeyink, 1997]. It remains open whether both bounds can be improved simultaneously to linear space and logarithmic query time. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p13.

Reference papers

Point locationJack SnoeyinkHandbook of Discrete and Computational Geometry · 1997

Point Location in 3D Subdivision

Coming soon

Organizer