Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram

DOI10.1007/BF01840348zbMath0631.68042OpenAlexW2025475855MaRDI QIDQ1094871

Micha Sharir, Chee-Keng Yap, Colm P. O'Dunlaing

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

configuration spaceroboticscomputational geometrygeneralized Voronoi diagramladder-moving problemmotion-planning algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Other problems of combinatorial convexity (52A37) Polytopes and polyhedra (52Bxx)

Related Items (18)

An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments ⋮ Planar realizations of nonlinear Davenport-Schinzel sequences by segments ⋮ Simplified Voronoi diagrams ⋮ On-line motion planning: Case of a planar rod ⋮ Coordinated motion planning for two independent robots ⋮ A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space ⋮ On the geodesic Voronoi diagram of point sites in a simple polygon ⋮ Construction of optimal programmed paths for the motion of a robotic manipulator ⋮ Improved lower bounds on the length of Davenport-Schinzel sequences ⋮ A survey of motion planning and related geometric algorithms ⋮ The complexity of planar compliant motion planning under uncertainty ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ 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 ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ Rods and Rings: Soft Subdivision Planner for R^3 x S^2. ⋮ On soft predicates in subdivision motion planning

Cites Work

• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• 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
• On a problem of Davenport and Schinzel
• A Combinatorial Problem Connected with Differential Equations
• A combinatorial problem connected with differential equations II

This page was built for publication: Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram