ISSN:
1432-0541
Keywords:
Link distance
;
Shortest paths
;
Motion planning
;
Computational geometry
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758855
Permalink
