Piecewise linear paths among convex obstacles |
| |
Authors: | M de Berg J Matou?ek O Schwarzkopf |
| |
Institution: | 1. Vakgroep Informatica, Universiteit Utrecht, Postbus 80.089, 3508 TB, Utrecht, The Netherlands 2. Katedra aplikované matematiky, Universita Karlova, Malostranské nám. 25, 180 00, Praha 1, Czech Republic 3. Institut für Informatik, Freie Universit?t Berlin, Arnimallee 2-6, D-14195, Berlin 33, Germany
|
| |
Abstract: | Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ
d
. It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path
consisting ofO(n
(d−1)d/2+1]) segments. The bound cannot be improved below Ω(n
d
); thus, in ℝ3, the answer is betweenn
3 andn
4. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational
motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given
in the planar case.
This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III
Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research
was done while he visited Utrecht University. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|