REU: Algorithms for Dynamic Point Location, ALADDIN Center

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)

Preliminary Presentation (ppt)
Final Presentation (ppt)

Other REUs for Summer 2004

Algorithms for Dynamic Point Location with Good Practical Performance
A Bezier-Based Approach to Unstructured Moving Meshes
Evaluation of Algorithms for the List Update Problem
Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)
Fast and Compact Data Structures
The Game of NimG (Nim on Graphs)
Random Graph Models of Large Real-World Networks
Solving Partial Differential Equations Numerically
Traceable Anonymity

Back to the REU page