Distance-sensitive planar point location (Q283883): Difference between revisions

One of the most fundamental problems in computational geometry is point location. The authors consider one of its variants, namely the distance-sensitive point location. In this variant we have a subdivision \(S\) and we want to preprocess it so that we can determine efficiently which region of \(S\) contains a query point \(p\) and the query time relates to the distance of \(p\) to the nearest point on the boundary of the region that contains it. The paper starts with the description of how to construct a distance sensitive point location structure. The construction is divided into two steps. In the first step, the authors create a distance-sensitive decomposition for the polygons of the input subdivision. A distance-sensitive decomposition of a simple polygon \(P\) with \(n\) edges consists of \(O(n)\) regions with the following properties: (1) each region \(R\) is convex and has constant complexity, (2) for some absolute constant \(\alpha\) the decomposition has the \(\alpha\)-distance property, i.e., for any point \(p \in P\), the region \(R\) containing \(p\) has an area at least \(\alpha \cdot \Delta^{2}_{p}\), where \(\Delta_p\) is the Euclidean distance from \(p\) to the boundary of \(P\). Having the distance-sensitive decomposition, in the second step, the authors use the entropy-based structure introduced by \textit{S. Arya} et al. [SIAM J. Comput. 37, No. 2, 584--610 (2007; Zbl 1137.68021)], where the probabilities for the regions are equal to \(\gamma_i = \mathrm{area}(R) /\mathrm{area}(P_i)\), where \(P_i \in S\) and \(R\) is a region that belongs to the distance-sensitive decomposition of \(P_i\). Because the main step in the presented algorithm is the construction of a distance-sensitive decomposition, the authors focus on algorithms for constructing such decompositions. They start with the algorithm for convex polygons and next they deal with the case of simple polygons. Next, they prove that the decomposition can be computed in \(O(n \log n)\) time and that we can obtain a linear-size data structure for point location in a planar connected polygonal subdivision such that the query time for a point \(p\) in polygon \(P_i \in S\) is \(O(\min(\log n, 1+ \log {\mathrm{area}(P_i) \over \gamma_i \Delta_{p}^{2}}))\). Then, the authors investigate a special case in which the query bound is based only on the distance of a query point to the boundary. They make an assumption that the subdivision is contained in a square of area \(1\) and present a data structure that achieves a query time of \(O(\min (\log n, 1 + \log {1 \over \Delta_{p}^{2}}))\) for a point \(p\). The structure is based on a depth-bounded quadtree and a worst-case optimal point location structure, that can be constructed in \(O(n \log n)\) time and \(O(n)\) space. At the end the authors consider the extension of the simpler data structure to three dimensions. They show that for a given convex polyhedral subdivision (with \(n\) edges) contained in a unit cube we can construct a distance-sensitive point location structure in \(O(n \log^2 n)\) time and \(O(n \log n)\) space that answers a query for a point \(p\) in \(O(1 + \log {1 \over \Delta_{p}^{2}})\) time if \(\Delta_p \geq \sqrt{3} / \root 3 \of {n}\) and \(O(\log^2 n)\) otherwise.