Name
Title | ||
|---|---|---|
Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures |
Abstract | ||
|---|---|---|
We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time &OHgr;(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time &ogr;((a/b · 1/&egr; crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and &egr;crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is &Ogr;(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/BF01758853 | Algorithmica |
Keywords | Field | DocType |
boundary complexity,motion planning,computational geometry,combinatorial geometry,analysis of algorithms. | Motion planning,Mathematical optimization,Algebra,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 5&6 | 1432-0541 |
Citations | PageRank | References |
39 | 3.93 | 8 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| helmut alt | 1 | 260 | 51.08 |
| Rudolf Fleischer | 2 | 949 | 85.69 |
| Michael Kaufmann | 3 | 42 | 4.49 |
| Kurt Mehlhorn | 4 | 5314 | 853.36 |
| Stefan Näher | 5 | 961 | 146.99 |
| Stefan Schirra | 6 | 509 | 70.29 |
| Christian Uhrig | 7 | 739 | 99.73 |