Abstract
We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in M. The space requirement is O (n log n). Point-location queries take time O (log n). Ray-shooting and shortest-path queries take time O (log3n) (plus O(k) time if the k edges of the shortest path are reported in addition to its length). Updates consist of insertions and deletions of vertices and edges, and take O(log3n) time (amortized for vertex updates). This is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. It is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.
Original language | English (US) |
---|---|
Pages (from-to) | 207-233 |
Number of pages | 27 |
Journal | SIAM Journal on Computing |
Volume | 25 |
Issue number | 1 |
DOIs | |
State | Published - Feb 1996 |
Keywords
- Computational geometry
- Dynamic algorithm
- Point location
- Ray shooting
- Shortest path
ASJC Scopus subject areas
- General Computer Science
- General Mathematics