On critical orientations in the Kedem-Sharir motion planning algorithm

DOI10.1007/BF02770875zbMath0871.68160OpenAlexW2028348452MaRDI QIDQ677023

Sivan Toledo, Micha Sharir, Klara Kedem

Publication date: 23 March 1997

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

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

zbMATH Keywords

motion planning algorithm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Combinatorial complexity of translating a box in polyhedral 3-space

Cites Work

• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Extremal polygon containment problems
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space