The complexity of the free space for a robot moving amidst fat obstacles
From MaRDI portal
Publication:1314536
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
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