On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds

DOI10.1016/0196-8858(83)90014-3zbMath0554.51008OpenAlexW2033013465MaRDI QIDQ760006

Publication date: 1983

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-8858(83)90014-3

zbMATH Keywords

algorithms decomposition geometric constraints topology robotics algebraic variety continuous motion collection of bodies sentences

Mathematics Subject Classification ID

Homology and cohomology theories in algebraic topology (55N99) Topological geometry (51H99)

Related Items (93)

New algorithms for multilink robot arms ⋮ Extremal polygon containment problems ⋮ Scalable distributed algorithms for multi-robot near-optimal motion planning ⋮ Castles in the air revisited ⋮ Ray shooting on triangles in 3-space ⋮ On boundaries of highly visible spaces and applications ⋮ Computing the Betti numbers of arrangements via spectral sequences ⋮ Dynamic path planning for a planar articulated robot arm moving amidst unknown obstacles ⋮ Reconfiguring closed polygonal chains in Euclidean \(d\)-space ⋮ Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram ⋮ Motion planning among time dependent obstacles ⋮ The complexity of elementary algebra and geometry ⋮ Partitioning and separating sets of orthogonal polygons ⋮ A search algorithm for motion planning with six degrees of freedom ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Geometry and search in motion planning. ⋮ CW Complexes for Complex Algebraic Surfaces ⋮ Simplified Voronoi diagrams ⋮ On-line motion planning: Case of a planar rod ⋮ Planning constrained motion ⋮ Coordinated motion planning for two independent robots ⋮ Motion planning in the presence of movable obstacles ⋮ A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space ⋮ Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape ⋮ An algorithm for generalized point location and its applications ⋮ A bibliography of quantifier elimination for real closed fields ⋮ An adjacency algorithm for cylindrical algebraic decompositions of three- dimensional space ⋮ A cluster-based cylindrical algebraic decomposition algorithm ⋮ Computer algebra applied to itself ⋮ Algorithmic and complexity issues of robot motion in an uncertain environment ⋮ A tight lower bound for the complexity of path-planning for a disc ⋮ The jogger's problem: Control of dynamics in real-time motion planning ⋮ A geometric approach to error detection recovery for robot motion planning with uncertainty ⋮ Algebraic decomposition of regular curves ⋮ Constructing roadmaps of semi-algebraic sets. I: Completeness ⋮ A biologically inspired neural net for trajectory formation and obstacle avoidance ⋮ A survey of motion planning and related geometric algorithms ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Numerical roadmap of smooth bounded real algebraic surface ⋮ OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS ⋮ Complexity of Control-Affine Motion Planning ⋮ Persistent Homology of Semialgebraic Sets ⋮ Regular cylindrical algebraic decomposition ⋮ Throwing a sofa through the window ⋮ CAD and topology of semi-algebraic sets ⋮ Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results ⋮ A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface ⋮ On the reconfiguration of chains ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Triangulating a nonconvex polytope ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ Geometric reasoning with logic and algebra ⋮ Divide and conquer roadmap for algebraic sets ⋮ Cylindrical algebraic sub-decompositions ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ A baby step-giant step roadmap algorithm for general algebraic sets ⋮ Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets ⋮ Construction of C-space roadmaps from local sensory data. What should the sensors look for? ⋮ Towards exact geometric computation ⋮ Robot motion planning with uncertainty in control and sensing ⋮ The Construction of Analytic Diffeomorphisms for Exact Robot Navigation on Star Worlds ⋮ A Simple Path Non-existence Algorithm Using C-Obstacle Query ⋮ Rapidly-exploring Sorted Random Tree: A Self Adaptive Random Motion Planning Algorithm ⋮ A real-time dual-arm collision avoidance algorithm for assembly ⋮ An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object ⋮ Validity proof of Lazard's method for CAD construction ⋮ Motion planning via manifold samples ⋮ Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets ⋮ Some aspects of complexity in real algebraic geometry ⋮ On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms ⋮ Entropy and complexity of a path in sub-Riemannian geometry ⋮ Truth table invariant cylindrical algebraic decomposition ⋮ Computing roadmaps of semi-algebraic sets on a variety ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Computing the homology of semialgebraic sets. II: General formulas ⋮ Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams ⋮ Cylindrical algebraic decomposition with equational constraints ⋮ Rods and Rings: Soft Subdivision Planner for R^3 x S^2. ⋮ Randomized query processing in robot path planning ⋮ Dynamic motion planning in low obstacle density environments ⋮ Dynamic motion planning in low obstacle density environments ⋮ Voronoi diagrams with barriers and on polyhedra for minimal path planning ⋮ Problem Formulation for Truth-Table Invariant Cylindrical Algebraic Decomposition by Incremental Triangular Decomposition ⋮ Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets ⋮ An approximation algorithm ford₁-optimal motion of a rod robot with fixed rotations ⋮ A computational method for determining strong stabilizability of \(n\)-D systems ⋮ Complete geometric query languages ⋮ Convex hulls of objects bounded by algebraic curves ⋮ Robot navigation functions on manifolds with boundary ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems ⋮ Local box adjacency algorithms for cylindrical algebraic decompositions ⋮ Description of the connected components of a semialgebraic set in single exponential time ⋮ On soft predicates in subdivision motion planning

Cites Work

This page was built for publication: On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds