The complexity of the free space for a robot moving amidst fat obstacles

DOI10.1016/0925-7721(93)90007-SzbMath0801.68177OpenAlexW2134898774MaRDI QIDQ1314536

Mark H. Overmars, A. Frank van der Stappen, Dan Halperin

Publication date: 17 February 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(93)90007-s

zbMATH Keywords

motion planningcomputational geometrycombinatorial complexityfree spacefatnessmultiple contacts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies and applications (68U99)

Related Items (23)

Models and motion planning ⋮ Median trajectories ⋮ New results on binary space partitions in the plane (extended abstract) ⋮ Range searching in low-density environments ⋮ On a class of \(O(n^ 2)\) problems in computational geometry ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ New results on binary space partitions in the plane ⋮ Exact and approximation algorithms for computing optimal fat decompositions ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Maximum matchings in geometric intersection graphs ⋮ On a class of \(O(n^2)\) problems in computational geometry ⋮ Unions of fat convex polytopes have short skeletons ⋮ Similarity of polygonal curves in the presence of outliers ⋮ Improved bounds on the union complexity of fat objects ⋮ Point location in fat subdivisions ⋮ Models and motion planning ⋮ Sampling-Based Motion Planning for Uncertain High-Dimensional Systems via Adaptive Control ⋮ Spheres, molecules, and hidden surface removal ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ Contraction and expansion of convex sets ⋮ Dynamic data structures for fat objects and their applications ⋮ The complexity of the free space for motion planning amidst fat obstacles ⋮ The complexity of the free space for a robot moving amidst fat obstacles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• 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
• 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
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• Efficient Motion Planning for an L-Shaped Object

This page was built for publication: The complexity of the free space for a robot moving amidst fat obstacles