The dynamic point location problem is a classic
problem in computational geometry. Given a subdivision of the
plane, the problem is to locate the face containing a given point,
while also supporting insertions and deletions of segments. The
problem has been studied extensively; yet no data structures have
been found that can support both queries and insertions/deletions
in O(logn) time. Best algorithms take O(log^2(n)) for either the
queries or the insertions. We recently developed a simple randomized
algorithm that can support queries in O(logn) time and insertions/deletions
in time that is based on certain characteristics of the input
(the subdivision) and the line-segment inserted or deleted. The
algorithm is therefore input sensitive—its performance depends
on the input. We expect that the algorithm will achieve O(logn)
time for insertions/deletions and queries for many real-world
instances of the point-location problem. The algorithm is obtained
by dynamizing the persistent point location data structure of
Sarnak and Tarjan [1] using novel techniques.
In this project, we are implementing the algorithm and evaluating
its performance on some real-world problems, such as maps used
in geographic information systems. We expect that this work will
result in a better understanding of the practical value of the
dynamization technique used in this algorithm and possibly lead
to other input-sensitive algorithms that are more efficient in
practice than their worst-case counterparts.
[1] Neil Sarnak and Robert Endre Tarjan, Planar
Point Location Using Persistent Search Trees, Communications
of the ACM 29(7): 669-679 (1986)
This material is based upon work supported by National Science
Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation