Optimal piecewise linear motion of an object among obstacles

DOI10.1007/BF01840372zbMath0637.68082OpenAlexW2057364504MaRDI QIDQ1098643

Ellen B. Silverberg, Christos H. Papadimitriou

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

motion planningpiano movers problemshortest-path motion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Discrete mathematics in relation to computer science (68R99) Topological geometry (51H99)

Related Items

An algorithmic approach to some problems in terrain navigation ⋮ Shortest paths for line segments ⋮ A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder ⋮ Characterizing the shortest path of an object among obstacles ⋮ An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• An algorithm for shortest-path motion in three dimensions
• 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
• Finding minimum rectilinear distance paths in the presence of barriers
• Fibonacci heaps and their uses in improved network optimization algorithms