Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

DOI10.1007/BF01758853zbMath0760.68082OpenAlexW2027190503MaRDI QIDQ1201745

Stefan Näher, Rudolf Fleischer, Stefan Schirra, Kurt Mehlhorn, Michael Kaufmann, Christian Uhrig, Helmut Alt

Publication date: 17 January 1993

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

motion planningrectangleobstacles

Mathematics Subject Classification ID

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

Related Items

Models and motion planning, Generalized disk graphs, On the union complexity of families of axis-parallel rectangles with a low packing number, Two- and three- dimensional point location in rectangular subdivisions, Computing depth orders and related problems, An optimal-time algorithm for shortest paths on realistic polyhedra, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Computing depth orders for fat objects and related problems, On fat partitioning, fat covering and the union size of polygons, On realistic terrains, On \(k\)-sets in arrangements of curves and surfaces, Improved bounds on the union complexity of fat objects, Simultaneous inner and outer approximation of shapes, Models and motion planning, 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, Visibility of rectagular objects inL₁metric, The complexity of the free space for a robot moving amidst fat obstacles

Cites Work

• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• On the general motion-planning problem with two degrees of freedom
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Optimal Point Location in a Monotone Subdivision