An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

DOI10.1007/BF02187779zbMath0688.68039OpenAlexW1997271799MaRDI QIDQ1263972

Klara Kedem, Micha Sharir

Publication date: 1990

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

Full work available at URL: https://eudml.org/doc/131106

zbMATH Keywords

computational geometrypolygonal obstaclestime-complexitypolygon motion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items

Extremal polygon containment problems, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Coordinated motion planning for two independent robots, Separating two simple polygons by a sequence of translations, A survey of motion planning and related geometric algorithms, 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, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Polygon placement under translation and rotation, On critical orientations in the Kedem-Sharir motion planning algorithm, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, A convex polygon among polygonal obstacle: Placement and high-clearance motion, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, On the general motion-planning problem with two degrees of freedom, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space, The complexity of the free space for motion planning amidst fat obstacles, Robot motion planning and the single cell problem in arrangements, 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, Translating a convex polyhedron over monotone polyhedra

Cites Work

• Unnamed Item
• 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
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• Improved lower bounds on the length of Davenport-Schinzel sequences
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• A “retraction” method for planning the motion of a disc
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• Solving the two-dimensional findpath problem using a line-triangle representation of the robot
• On a problem of Davenport and Schinzel