Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
From MaRDI portal
Publication:1094871
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
configuration spaceroboticscomputational geometrygeneralized Voronoi diagramladder-moving problemmotion-planning algorithm
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
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
