Point Location in 3D Subdivision

Let $n\in\mathbb{N}$ be the number of faces in a three-dimensional subdivision. Determine whether there is a point-location data structure for the subdivision that occupies $O(n)$ space and answers each point-location query in $O(\log n)$ time.

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