ISSN:
1432-0541
Keywords:
Shortest paths
;
Voronoi diagrams
;
Rectilinear paths
;
Wire routing
;
Fixed orientation metrics
;
Continuous Dijkstra algorithm
;
Computational geometry
;
Extremal graph theory
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We present an algorithm for computingL 1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2 log2 n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL 1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758836
