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.
Article PDF
Similar content being viewed by others
References
B. Aronov and M. Sharir, Triangles in space, or building (and analyzing) castles in the air,Combinatorica 10 (1990), 137–173.
B. Aronov and M. Sharir, Castles in the air revisited,Discrete Comput. Geom. 12 (1994), 119–150.
L. P. Chew and K. Kedem, A convex polygon among polygonal obstacles: placement and high-clearance motion,Comput. Geom. Theory Appl. 3(2) (1993), 59–89.
M. de Berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction,Discrete Comput. Geom. 14 (1995), 261–286.
L. Guibas and M. Sharir, Combinatorics and algorithms of arrangements, inNew Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, New York, 1993, pp. 9–36.
D. Halperin, Algorithmic Motion Planning via Arrangements of Curves and of Surfaces, Ph.D. Dissertation, Computer Science Department, Tel Aviv University, July 1992.
D. Halperin and M. Sharir, Arrangements and their applications in robotics: recent developments, inThe Algorithmic Foundations of Robotics (K. Goldberg, D. Halperin, J.-C. Latombe, and R. Wilson, eds.), A. K. Peters, Boston, MA, 1995, pp. 495–511.
D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions,Discrete Comput. Geom. 14 (1995), 385–410.
K. Kedem and M. Sharir, An efficient motion-planning algorithm for a convex polygonal object in twodimensional polygonal space,Discrete Comput. Geom. 5 (1990), 43–75.
K. Kedem, M. Sharir, and S. Toledo, On critical orientations in the Kedem-Sharir motion planning algorithm for a convex polygon in the plane,Proc. 5th Canadian Conf. on Computational Geometry, 1993, pp. 204–209.
D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object moving in 2-D polygonal space,Discrete Comput. Geom. 2 (1987), 255–270.
J. Matoušek, Approximations and optimal geometric divide-and-conquer,Proc. 23rd ACM Symp. on Theory of Computing, 1991, pp. 502–511.
J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem,J. Symbolic Comput. 10(1990), 371–393.
M. Sharir and P.K. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995.
M. Sharir and S. Toledo, Extremal polygon containment problems,Comput. Geom. Theory Appl. 4 (1994), 99–118.
D. D. Sleator, R. E. Tarjan, and W. P. Thurston, Rotation distance, triangulations, and hyperbolic geometry,J. Amer. Math. Soc. 1 (1988), 647–681.
R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Halperin, D., Sharir, M. A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment. Discrete Comput Geom 16, 121–134 (1996). https://doi.org/10.1007/BF02716803
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02716803