Paper Info
Title
Optimal Shortest Path And Minimum-Link Path Queries Between Two Convex Polygons Inside A Simple Polygonal Obstacle
Abstract
We present efficient algorithms for shortest-path and minimum-link-path queries between two convex polygons inside a simple polygon P, which acts as an obstacle to be avoided. Let n be the number of vertices of P, and h. the total number of vertices of the query polygons. We show that shortest-path queries can be performed optimally in time O (log h + log n) (plus O (k) time for reporting the k edges of the path) using a data structure with O(n) space and preprocessing time, and that minimum-link-path queries can be performed in optimal time O (log h + log n) (plus O (k) to report the k links), with O (n(3)) space and preprocessing time.We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision S. The update operations consist of insertions and deletions of edges and vertices. Let n be the current number of vertices in S. The data structure uses O(n) space, supports updates in O (log(2) n) time, and performs shortest-path and minimum-link-path queries in times O (log h + log(2) n) (plus O(k) to report the k edges of the path) and O(log h + k log(2) n), respectively. Performing shortest-path queries is a variation of the well-studied separation problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries.
Year
DOI
Venue
1997
10.1142/S0218195997000077
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
Keywords
DocType
Volume
computational geometry, shortest path, minimum-link path, static and dynamic data structures, analysis of algorithms
Journal
7
Issue
ISSN
Citations 
1-2
0218-1959
3
PageRank 
References 
Authors
0.40
0
2
Name
Order
Citations
PageRank
Yi-jen Chiang150338.21
R Tamassia24686550.39