Construction of roadmaps in semi-algebraic sets

DOI10.1007/BF01200148zbMath0807.14047MaRDI QIDQ1311619

L. Gournay, Jean-Jacques Risler

Publication date: 5 March 1995

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

compact semialgebraic setconstruction of a roadmap

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of algebraic curves (14Q05) Semialgebraic sets and related spaces (14P10)

Related Items (13)

Algorithms to compute the topology of orientable real algebraic surfaces ⋮ Numerical roadmap of smooth bounded real algebraic surface ⋮ A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ 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 ⋮ Computing roadmaps of semi-algebraic sets on a variety ⋮ Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ Description of the connected components of a semialgebraic set in single exponential time

Cites Work

• Definability and fast quantifier elimination in algebraically closed fields
• Generalised characteristic polynomials
• Solving systems of polynomial inequalities in subexponential time
• Constructing roadmaps of semi-algebraic sets. I: Completeness
• Complexity of deciding Tarski algebra
• On the Betti Numbers of Real Varieties
• Finding connected components of a semialgebraic set in subexponential time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Construction of roadmaps in semi-algebraic sets