Computing roadmaps of semi-algebraic sets on a variety

DOI10.1090/S0894-0347-99-00311-2zbMath0933.14037OpenAlexW1589087843MaRDI QIDQ4700178

Saugata Basu, Marie-Françoise Roy, Richard Pollack

Publication date: 1 November 1999

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0894-0347-99-00311-2

zbMATH Keywords

complexitypathsemi-algebraic setsroadmaps

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10)

Related Items (27)

Algorithms to compute the topology of orientable real algebraic surfaces ⋮ Computing the Betti numbers of arrangements via spectral sequences ⋮ Numerical roadmap of smooth bounded real algebraic surface ⋮ Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics ⋮ Algorithm for Connectivity Queries on Real Algebraic Curves ⋮ Persistent Homology of Semialgebraic Sets ⋮ Efficient simplicial replacement of semialgebraic sets ⋮ Variant quantifier elimination ⋮ A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface ⋮ Topology of real multi-affine hypersurfaces and a homological stability property ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ Geodesic diameter of sets defined by few quadratic equations and inequalities ⋮ Divide and conquer roadmap for algebraic sets ⋮ Computing the first few Betti numbers of semi-algebraic sets in single exponential time ⋮ A baby step-giant step roadmap algorithm for general algebraic sets ⋮ Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time ⋮ Computing the first Betti number of a semi-algebraic set ⋮ Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets ⋮ Unnamed Item ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Unnamed Item ⋮ On a real analog of Bezout inequality and the number of connected components of sign conditions ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets ⋮ Special algorithm for stability analysis of multistable biological regulatory systems ⋮ Bounding the length of gradient trajectories

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Constructing roadmaps of semi-algebraic sets. I: Completeness
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Counting connected components of a semialgebraic set in subexponential time
• Nash triviality in families of Nash manifolds
• Construction of roadmaps in semi-algebraic sets
• Finding irreducible components of some real transcendental varieties
• On computing a set of points meeting every cell defined by a family of polynomials on a variety
• Computing Roadmaps of General Semi-Algebraic Sets
• Morse Theory. (AM-51)
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• On the combinatorial and algebraic complexity of quantifier elimination
• Finding at least one point in each connected component of a real algebraic set defined by a single equation
• Finding connected components of a semialgebraic set in subexponential time

This page was built for publication: Computing roadmaps of semi-algebraic sets on a variety