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

DOI10.1007/BF02187779zbMath0688.68039MaRDI 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 geometry; polygonal obstacles; time-complexity; polygon motion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U99: Computing methodologies and applications

Related Items

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, On critical orientations in the Kedem-Sharir motion planning algorithm, A convex polygon among polygonal obstacle: Placement and high-clearance motion, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Separating two simple polygons by a sequence of translations, A survey of motion planning and related geometric algorithms, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, 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 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, Extremal polygon containment problems, Coordinated motion planning for two independent robots, Combinatorial complexity of translating a box in polyhedral 3-space, 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, Translating a convex polyhedron over monotone polyhedra, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Polygon placement under translation and rotation

Cites Work

• 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
• Unnamed Item