A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment |
| |
Authors: | D. Halperin M. Sharir |
| |
Affiliation: | (1) Robotics Laboratory, Department of Computer Science, Stanford University, 94305 Stanford, CA, USA;(2) School of Mathematical Sciences, Tel Aviv University, 69978 Tel Aviv, Israel;(3) Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(4) Present address: Department of Computer Science, Tel Aviv University, 69978 Tel Aviv, Israel |
| |
Abstract: | We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn) 2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion-planning problem, within the same running time. Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|