THESIS
2020

ix, 124 pages : illustrations ; 30 cm

**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. I...[

Read more ]

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

^{2}, 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

^{5} 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

^{2} n). As a corollary, the randomized incremental
construction of the Voronoi diagram of n sites can be performed in O(n log

^{5} 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

^{8} n + log

^{31} n) amortized time to perform a subdivision update.

## Post a Comment

Your email address will not be published. Required fields are marked *