A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

DOI10.1007/BF01840368zbMath0643.68049OpenAlexW2061311037MaRDI QIDQ1102109

Micha Sharir, Shmuel Sifrony

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840368

zbMATH Keywords

configuration spaceroboticscomputational geometryladderpolygonal obstaclesmotion-planning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04)

Related Items (17)

On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles ⋮ The visibility diagram: A data structure for visibility problems and motion planning ⋮ On-line motion planning: Case of a planar rod ⋮ Coordinated motion planning for two independent robots ⋮ Separating two simple polygons by a sequence of translations ⋮ Lower bounds on moving a ladder in two and three dimensions ⋮ A survey of motion planning and related geometric algorithms ⋮ Polygon placement under translation and rotation ⋮ Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom ⋮ Simple wriggling is hard unless you are a fat hippo ⋮ On the general motion-planning problem with two degrees of freedom ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder ⋮ The complexity of the free space for motion planning amidst fat obstacles ⋮ An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations ⋮ On the complexity of a single cell in certain arrangements of surfaces related to motion planning ⋮ The complexity of the free space for a robot moving amidst fat obstacles

Cites Work

• Unnamed Item
• Unnamed Item
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• 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
• Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
• 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

This page was built for publication: A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space