ISSN:
1432-0541
Keywords:
Computational geometry
;
Motion planning
;
Boundary complexity
;
Combinatorial geometry
;
Analysis of algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n 2), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/ɛcrit + 1)n(logn)2), wherea ≥b are the lengths of the sides of a rectangle and ɛcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758853
Permalink