Abstract
We show that, under reasonable assumptions, any collision-avoiding motion-planning problem for a moving system with two degrees of freedom can be solved in timeO(λ s (n) log2 n), wheren is the number of collision constraints imposed on the system,s is a fixed parameter depending, e.g., on the maximum algebraic degree of these constraints, andλ s (n) is the (almost linear) maximum length of (n, s) Davenport-Schinzel sequences. This follows from an upper bound ofO(λ s (n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.
Article PDF
Similar content being viewed by others
References
P. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences, Tech. Rept. 332, Comput. Science Dept., Courant Institute, New York, 1987. (To appear inJ. Combin. Theory Ser. A.)
P. Agarwal and M. Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 70–80.
B. Aronov and M. Sharir, Triangles in space, or: Building (and analyzing) castles in the air,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 381–391. (Also to appear inCombinatorica.)
M. Atallah, Dynamic computational geometry,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 92–99. Also inComput. Math. Appl. 11 (1985), pp. 1171–1181.
J. L. Bentley and T. Ottmann, Algorithm for reporting and counting geometric intersections,IEEE Trans. Comput. 28 (1979), pp. 643–647.
B. Bhattacharya and J. Zorbas, Solving the two-dimensional findpath problem using a line-triangle representation of the robot,J. Algorithms 9 (1988), pp. 449–469.
B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 590–600.
B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 135–146.
K. Clarkson, Applications of random sampling in computational geometry, II,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 1–11.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 568–579.
H. Edelsbrunner and L. Guibas, Topologically sweeping an arrangement,Proc. 18th ACM Symposium on Theory of Computing, 1986, pp. 389–403.
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Discrete Comput. Geom. (1989), this issue, pp. 433–436.
H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, On arrangements of Jordan arcs with three intersections per pair,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 258–265.
H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of arcs in the plane: Topology, combinatorics, and algorithms,Proc. 15th Int. Colloq. on Automata, Languages and Programming, 1988, pp. 214–229.
H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of lines or of segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 44–55.
H. Edelsbrunner and M. Sharir, The maximum number of ways to stabn disjoint convex sets in the plane is 2n−2, Tech. Rept. 281, Comput. Sci. Dept., Courant Institute, New York, 1987 (to appear inDiscrete Comput. Geom.).
S. Fortune, G. Wilfong, and C. Yap, Coordinated motion of two robot arms,Proc. IEEE Conf. on Robotics and Automation, 1986, pp. 1216–1223.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica 6 (1986), pp. 151–177.
R. Hartshorne,Algebraic Geometry, Springer-Verlag, New York, 1977.
K. Kedem and M. Sharir, Efficient algorithm for planning translational collision-free motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles,Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 75–80.
K. Kedem and M. Sharir, An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, to appear inDiscrete Comput. Geom.
K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom. 1 (1986), pp. 59–71.
D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,J. Algorithms 8 (1987), pp. 192–215.
D. Leven and M. Sharir, Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom. 2 (1987), pp. 9–31.
K. Mulmuley, A fast planar partition algorithm, I,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 590–600.
K. Mulmuley, A fast planar partition algorithm, II,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 33–43.
C. Ó'Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: I. Topological considerations,Comm. Pure Appl. Math. 39 (1986), pp. 423–483.
C. Ó'Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram,Algorithmica 2 (1987), pp. 29–57.
C. Ó'Dúnlaing and C. Yap, A “retraction” method for planning the motion of a disc,J. Algorithms 6 (1985), pp. 104–111.
J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: combinatorial analysis,Discrete Comput. Geom. 4 (1989), pp. 291–309.
R. Pollack, M. Sharir, and S. Sifrony, Separating two simple polygons by a sequence of translations,Discrete Comput. Geom. 3 (1988), pp. 123–136.
J. T. Schwartz and M. Sharir, On the piano movers' problem: I. The case of a rigid polygonal body moving amidst polygonal barriers,Comm. Pure Appl. Math. 36 (1983), pp. 345–398.
J. T. Schwartz and M. Sharir, On the piano movers' problem: II. General techniques for calculating topological properties of real algebraic manifolds,Adv. in Appl. Math. 4 (1983), pp. 298–351.
J. T. Schwartz and M. Sharir, On the piano movers' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers,Internat. J. Robotics Res. 2 (1983) (3), pp. 46–75.
J. T. Schwartz and M. Sharir, On the piano movers' problem: V. The case of a rod moving in 3-D space amidst polyhedral obstacles,Comm. Pure Appl. Math. 37 (1984), pp. 815–848.
J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem, Tech. Rept. 193 (revised), Comput. Sci. Dept., Courant Institute, New York, 1987. (To appear inJ. Symbolic Computation.)
M. Sharir and E. Ariel-Sheffi, On the piano movers' problem: IV. Various decomposable two-dimensional motion-planning problems,Comm. Pure Appl. Math. 37 (1984), pp. 479–493.
M. Sharir and S. Sifrony, Coordinated motion planning for two independent robots,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 319–328.
P. Shor, Geometric realizations of superlinear Davenport-Schinzel sequences, in preparation.
S. Sifrony, Efficient algorithms for motion-planning problems in robotics, Ph.D. Dissertation, Tel Aviv University, 1989.
S. Sifrony, Efficient algorithms for motion planning of certain spatial 3-DOF manipulator arms, manuscript, 1989.
S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in 2-D polygonal space,Algorithmica 2 (1987), pp. 367–402.
A. Wiernik and M. Sharir, Planar realization of nonlinear Davenport-Schinzel sequences by segments,Discrete Comput. Geom. 3 (1988), pp. 15–47.
Author information
Authors and Affiliations
Additional information
Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the second and third authors has also been supported by a research grant from the Joint Ramot-Israeli Ministry of Industry Foundation, and by a research grant from the NCRD—the Israeli National Council for Research and Development.
Rights and permissions
About this article
Cite this article
Guibas, L.J., Sharir, M. & Sifrony, S. On the general motion-planning problem with two degrees of freedom. Discrete Comput Geom 4, 491–521 (1989). https://doi.org/10.1007/BF02187744
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187744