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

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