A survey of motion planning and related geometric algorithms
From MaRDI portal
Publication:1123032
DOI10.1016/0004-3702(88)90053-7zbMath0676.68086OpenAlexW2011890292MaRDI QIDQ1123032
Micha Sharir, Jacob T. Schwartz
Publication date: 1988
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(88)90053-7
Related Items
Sets of lines and cutting out polyhedral objects ⋮ Time-optimal trajectories of a rod in the plane subject to velocity constraints ⋮ A bibliography of quantifier elimination for real closed fields ⋮ From LP to LP: Programming with constraints ⋮ A strong-connectivity algorithm and its applications in data flow analysis ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Construction of C-space roadmaps from local sensory data. What should the sensors look for? ⋮ Robot motion planning with uncertainty in control and sensing ⋮ Computing the homology of semialgebraic sets. I: Lax formulas
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Strong NP-hardness of moving many discs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- An algorithm for shortest-path motion in three dimensions
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
- Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
- Motion planning among time dependent obstacles
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
- Separating two simple polygons by a sequence of translations
- Improved lower bounds on the length of Davenport-Schinzel sequences
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- On the two-dimensional Davenport-Schinzel problem
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles
- Voronoi Diagram in the Laguerre Geometry and Its Applications
- A “retraction” method for planning the motion of a disc
- Euclidean shortest paths in the presence of rectilinear barriers
- Spatial Planning: A Configuration Space Approach
- Intersection and Closest-Pair Problems for a Set of Planar Discs
- Movement Problems for 2-Dimensional Linkages
- On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems
- Reducing Multiple Object Motion Planning to Graph Searching
- On the Movement of Robot Arms in 2-Dimensional Bounded Regions
- Generalized voronoi diagrams for moving a ladder. I: Topological analysis
- On Shortest Paths in Polyhedral Spaces
- On Shortest Paths Amidst Convex Polyhedra
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
- On the shortest paths between two convex polyhedra
- On a problem of Davenport and Schinzel
- Motion planning in the presence of moving obstacles
- A Combinatorial Problem Connected with Differential Equations
- A combinatorial problem connected with differential equations II
- Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix
