A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment

DOI10.1007/BF02716803zbMath0860.68111MaRDI QIDQ1923770

Dan Halperin, Micha Sharir

Publication date: 13 October 1996

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

zbMATH Keywords

motion-planning problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

Motion planning via manifold samples

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On critical orientations in the Kedem-Sharir motion planning algorithm
• A convex polygon among polygonal obstacle: Placement and high-clearance motion
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Extremal polygon containment problems
• Castles in the air revisited
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
• Almost tight upper bounds for the single cell and zone problems in the three dimensions
• On the two-dimensional Davenport-Schinzel problem
• Triangles in space or building (and analyzing) castles in the air
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• On lazy randomized incremental construction

This page was built for publication: A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment