Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams

DOI10.1007/BF02187867zbMath0606.52002OpenAlexW1975114110MaRDI QIDQ1084674

Daniel Leven, Micha Sharir

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131006

zbMATH Keywords

motion planningefficient algorithmgeneralized Voronoi diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (37)

Computing the smallest \(k\)-enclosing circle and related problems ⋮ Extremal polygon containment problems ⋮ Voronoi diagrams over dynamic scenes ⋮ An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments ⋮ Computing the smallest k-enclosing circle and related problems ⋮ A sweepline algorithm for Voronoi diagrams ⋮ On-line motion planning: Case of a planar rod ⋮ A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space ⋮ Separating two simple polygons by a sequence of translations ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ Voronoi-like partition of lattice in cellular automata ⋮ Construction of optimal programmed paths for the motion of a robotic manipulator ⋮ A survey of motion planning and related geometric algorithms ⋮ Hunting Voronoi vertices ⋮ Deconstructing approximate offsets ⋮ Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions ⋮ Stable Delaunay graphs ⋮ On the computation of zone and double zone diagrams ⋮ Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function ⋮ The upper envelope of piecewise linear functions: Algorithms and applications ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Stability of solutions in problems of computational geometry ⋮ An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles ⋮ A convex polygon among polygonal obstacle: Placement and high-clearance motion ⋮ Approximate motion planning and the complexity of the boundary of the union of simple geometric figures ⋮ Polygon decomposition for efficient construction of Minkowski sums ⋮ Convex-straight-skeleton Voronoi diagrams for segments and convex polygons ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Penny-packing and two-dimensional codes ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ On the construction of abstract Voronoi diagrams ⋮ On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ The geometry of Minkowski spaces -- a survey. II. ⋮ AN ALGEBRA FOR SLOPE-MONOTONE CLOSED CURVES ⋮ Unnamed Item ⋮ Approximating Voronoi Diagrams of Convex Sites in Any Dimension

Cites Work

• Unnamed Item
• Unnamed Item
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Spherical complexes and radial projections of polytopes
• 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
• Intersection and Closest-Pair Problems for a Set of Planar Discs

This page was built for publication: Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams