The complexity of the free space for motion planning amidst fat obstacles

DOI10.1007/BF01258292zbMath0816.68127OpenAlexW2152902216MaRDI QIDQ1842754

A. Frank van der Stappen

Publication date: 20 April 1995

Published in: Journal of Intelligent \& Robotic Systems (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial complexitymotion planning algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies and applications (68U99) Parallel algorithms in computer science (68W10)

Related Items (27)

Models and motion planning ⋮ Approximate unions of lines and Minkowski sums ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Range searching in low-density environments ⋮ An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Guarding scenes against invasive hypercubes. ⋮ Unions of fat convex polytopes have short skeletons ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains ⋮ On realistic terrains ⋮ Ray shooting and intersection searching amidst fat convex polyhedra in 3-space ⋮ Improved bounds on the union complexity of fat objects ⋮ Bounding the locus of the center of mass for a part with shape variation ⋮ Local polyhedra and geometric graphs ⋮ Placing Text Boxes on Graphs ⋮ Kinetic collision detection for convex fat objects ⋮ Dynamic motion planning in low obstacle density environments ⋮ Dynamic motion planning in low obstacle density environments ⋮ Decompositions and boundary coverings of non-convex fat polyhedra ⋮ Dynamic data structures for fat objects and their applications ⋮ The complexity of the free space for motion planning amidst fat obstacles ⋮ On the flatness of Minkowski sums ⋮ Walking around fat obstacles. ⋮ Reprint of: Bounding the locus of the center of mass for a part with shape variation

Cites Work

• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• Robot motion planning with uncertainty in control and sensing
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Point location in fat subdivisions
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• The complexity of the free space for a robot moving amidst fat obstacles
• The complexity of the free space for motion planning amidst fat obstacles
• 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
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• Efficient Motion Planning for an L-Shaped Object
• Fat Triangles Determine Linearly Many Holes

This page was built for publication: The complexity of the free space for motion planning amidst fat obstacles