Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

Yi Jen Chiang; Franco P. Preparata; Roberto Tamassia

Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

Yi Jen Chiang, Franco P. Preparata, Roberto Tamassia

Research output: Contribution to conference › Paper › peer-review

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(log³ n) (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(log³ n) time (amortized for vertex updates).

Original language	English (US)
Pages	44-53
Number of pages	10
State	Published - 1993
Event	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993

Other

Other	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
City	Austin, TX, USA
Period	1/25/93 → 1/27/93

ASJC Scopus subject areas

General Engineering

Cite this

@conference{21d938d2312d4e2381dc3ce2bb38e974,

title = "Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps",

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(log3 n) (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(log3 n) time (amortized for vertex updates).",

author = "Chiang, {Yi Jen} and Preparata, {Franco P.} and Roberto Tamassia",

year = "1993",

language = "English (US)",

pages = "44--53",

note = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1993 Through 27-01-1993",

}

TY - CONF

T1 - Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

AU - Chiang, Yi Jen

AU - Preparata, Franco P.

AU - Tamassia, Roberto

PY - 1993

Y1 - 1993

N2 - 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(log3 n) (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(log3 n) time (amortized for vertex updates).

AB - 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(log3 n) (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(log3 n) time (amortized for vertex updates).

UR - http://www.scopus.com/inward/record.url?scp=0027202918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027202918&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0027202918

SP - 44

EP - 53

T2 - Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 25 January 1993 through 27 January 1993

ER -

Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this