Computing Roadmaps of General Semi-Algebraic Sets

DOI10.1093/comjnl/36.5.504zbMath0798.14031MaRDI QIDQ3140561

John F. Canny

Publication date: 9 November 1994

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/36.5.504

zbMATH Keywords

complexity; roadmap algorithm; component of a semi-algebraic set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

14P10: Semialgebraic sets and related spaces

Related Items

Computing roadmaps of semi-algebraic sets on a variety, On the number of cells defined by a family of polynomials on a variety, Unnamed Item, Bounding the length of gradient trajectories, Variant quantifier elimination, A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, 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, Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials, Numerically computing real points on algebraic sets, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Computing the homology of semialgebraic sets. I: Lax formulas, On soft predicates in subdivision motion planning, Computing the first few Betti numbers of semi-algebraic sets in single exponential time