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

DOI10.1016/0925-7721(93)90007-SMaRDI QIDQ1314536zbMATH OpenOpenAlexFDO

Authors 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

combinatorial complexitycomputational geometryfatnessfree spacemotion planningmultiple 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)

Recommendations

• The complexity of the free space for motion planning amidst fat obstacles
• Models and motion planning
• Models and motion planning
• Motion planning in environments with low obstacle density
• scientific article; zbMATH DE number 3945381

Cites work

• A “retraction” method for planning the motion of a disc
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Efficient Motion Planning for an L-Shaped Object
• scientific article; zbMATH DE number 431984 (Why is no real title available?)
• scientific article; zbMATH DE number 4149525 (Why is no real title available?)
• scientific article; zbMATH DE number 3213790 (Why is no real title available?)
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
• Point location in fat subdivisions
• The complexity of the free space for a robot moving amidst fat obstacles

Cited in

(23)

• Contraction and expansion of convex sets
• Point location in fat subdivisions
• Spheres, molecules, and hidden surface removal
• The complexity of the free space for a robot moving amidst fat obstacles
• Range searching in low-density environments
• 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
• On fat partitioning, fat covering and the union size of polygons
• Models and motion planning
• The complexity of the free space for motion planning amidst fat obstacles
• On a class of \(O(n^ 2)\) problems in computational geometry
• Median trajectories
• Similarity of polygonal curves in the presence of outliers
• Sampling-based motion planning for uncertain high-dimensional systems via adaptive control
• On a class of O(n^2) problems in computational geometry
• Unions of fat convex polytopes have short skeletons
• Sublinear separators in intersection graphs of convex shapes
• Models and motion planning
• New results on binary space partitions in the plane (extended abstract)
• Dynamic data structures for fat objects and their applications
• Exact and approximation algorithms for computing optimal fat decompositions
• Maximum matchings in geometric intersection graphs
• Improved bounds on the union complexity of fat objects

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1314536)