Exploiting query distribution in planar point location

Abstract

Planar point location is a classical problem in computational geometry. Several point location algorithms are known that achieve optimal worst-case query time. However, there is still a lot of research on this topic. In many applications, certain regions in a planar subdivision are more frequently queried. This raises the question of whether a better query time can be obtained by exploiting the query distribution. In this thesis, we study the point location algorithms that exploit the query distribution to acheive a better query time. We study both the static and dynamic cases. In the static case, the given subdivision is fixed. In the dynamic case, the subdivision can be updated using edge insertions and deletions. Any new edge to be inserted does not cross any existing one. In the static case, most of the existing solutions assume that the query distribution is fixed and can be accessed quickly. In the scenario that the query distribution is not known in advance, we propose point location algorithms for convex and connected subdivisions that can process any online query sequence σ in Ο(OPT + n) and O(OPT + n + │ σ │ log(log* n)) time, respectively, where n is the number of subdivision vertices and OPT is the minimum time to answer queries in σ by any linear decision tree. In the dynamic case, nothing is known about how to exploit the query distribution in answering point location queries. Suppose that there is a fixed query distribution in R², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. A subdivision update is specified as a mixed sequence of k edge insertions and deletions. We can maintain a convex subdivision with n vertices such that it takes O(opt) expected time to answer a query and O(k log⁵ n) amortized time to perform a subdivision update, where opt is the minimum expected query time required by any linear decision tree to do a point location. The space and construction time are O(n log² n). As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query can be answered optimally with respect to the intermediate Voronoi diagram at that time. Similarly, we can maintain a connected subdivision with n vertices such that it takes O(opt + log(log* n)) expected time to answer a query and O(k log⁸ n + log³¹ n) amortized time to perform a subdivision update.

Date of Award	2020
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology