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

DOI10.1007/BF01840368zbMATH Open0643.68049OpenAlexW2061311037MaRDI QIDQ1102109FDOQ1102109

Authors: 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

Recommendations

• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations
• scientific article; zbMATH DE number 1777524
• A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
• A fast approach for robot motion planning
• A unified approach for robot motion planning with moving polyhedral obstacles
• Motion planning algorithms for configuration spaces in the higher dimensional case
• Efficient Motion Planning for an L-Shaped Object
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams

zbMATH Keywords

computational geometryconfiguration spaceroboticsladderpolygonal 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)

Cites Work

• Title not available (Why is that?)
• Algorithms for Reporting and Counting Geometric Intersections
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• 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
• A “retraction” method for planning the motion of a disc
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles
• Title not available (Why is that?)
• On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems

Cited In (24)

• Trajectory planning for an articulated probe
• A survey of motion planning and related geometric algorithms
• The visibility diagram: A data structure for visibility problems and motion planning
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Simple wriggling is hard unless you are a fat hippo
• On-line motion planning: Case of a planar rod
• Optimal piecewise linear motion of an object among obstacles
• Lower bounds on moving a ladder in two and three dimensions
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• Coordinated motion planning for two independent robots
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder
• Polygon placement under translation and rotation
• The complexity of the free space for a robot moving amidst fat obstacles
• Separating two simple polygons by a sequence of translations
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• On the general motion-planning problem with two degrees of freedom
• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• Motion Planning of Legged Robots
• An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations
• The complexity of the free space for motion planning amidst fat obstacles
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
• New algorithms for multilink robot arms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102109)