On the general motion-planning problem with two degrees of freedom

DOI10.1007/BF02187744zbMath0685.68049OpenAlexW1994094252MaRDI QIDQ1262130

Shmuel Sifrony, Leonidas J. Guibas, Micha Sharir

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131093

zbMATH Keywords

motion planningobstacle avoidance2 d.o.f. systemsingle face of Jordan curves

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other designs, configurations (05B30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Other problems of combinatorial convexity (52A37)

Related Items

Castles in the air revisited, Computing a single cell in the overlay of two simple polygons, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Excess in arrangements of segments, A new algorithm for shortest paths among obstacles in the plane, Coordinated motion planning for two independent robots, Almost tight upper bounds for the single cell and zone problems in the three dimensions, The common exterior of convex polygons in the plane, Combinatorial complexity of signed discs, Combinatorial complexity of translating a box in polyhedral 3-space, Preprocessing chains for fast dihedral rotations is hard or even impossible., Storing line segments in partition trees, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, An optimal algorithm for the boundary of a cell in a union of rays, The upper envelope of piecewise linear functions: Algorithms and applications, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, A convex polygon among polygonal obstacle: Placement and high-clearance motion, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, The number of edges of many faces in a line segment arrangement, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, The complexity and construction of many faces in arrangements of lines and of segments, On lazy randomized incremental construction, Combinatorial complexity of signed discs, On arrangements of Jordan arcs with three intersections per pair, Constrained Minkowski sums: A geometric framework for solving interval problems in computational biology efficiently, Robot motion planning and the single cell problem in arrangements, Minimum Cell Connection in Line Segment Arrangements, On the complexity of a single cell in certain arrangements of surfaces related to motion planning, Polyhedral Assembly Partitioning Using Maximally Covered Cells in Arrangements of Convex Polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Visibility and intersection problems in plane geometry
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Combinatorial complexity bounds for arrangements of curves and spheres
• Some dynamic computational geometry problems
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• Separating two simple polygons by a sequence of translations
• Topologically sweeping an arrangement
• On arrangements of Jordan arcs with three intersections per pair
• Implicitly representing arrangements of lines or segments
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Coordinated motion planning for two independent robots
• Triangles in space or building (and analyzing) castles in the air
• Algorithms for Reporting and Counting Geometric Intersections
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles
• A “retraction” method for planning the motion of a disc
• On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• Solving the two-dimensional findpath problem using a line-triangle representation of the robot
• An optimal algorithm for intersecting line segments in the plane