A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface

DOI10.1007/s00454-009-9239-2zbMath1213.14110OpenAlexW2592887901MaRDI QIDQ629823

Éric Schost, Mohab Safey El Din

Publication date: 10 March 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9239-2

zbMATH Keywords

complexityalgorithmscomputational real algebraic geometryroadmaps

Mathematics Subject Classification ID

Real algebraic sets (14P05) Semialgebraic sets and related spaces (14P10) Computational aspects in algebraic geometry (14Q99)

Related Items

Numerical roadmap of smooth bounded real algebraic surface, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Variant quantifier elimination, Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results, Divide and conquer roadmap for algebraic sets, Solving determinantal systems using homotopy techniques, A baby step-giant step roadmap algorithm for general algebraic sets, Rods and Rings: Soft Subdivision Planner for R^3 x S^2., Bit complexity for computing one point in each connected component of a smooth real algebraic set, Computing real witness points of positive dimensional polynomial systems

Uses Software

• Kronecker
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Les singularités des applications différentiables
• The theorem of Mather on generic projections in the setting of algebraic geometry
• Nash triviality in families of Nash manifolds
• Solving zero-dimensional systems through the rational univariate representation
• Construction of roadmaps in semi-algebraic sets
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Straight-line programs in geometric elimination theory
• Computing parametric geometric resolutions
• On the geometry of polar varieties
• Singularities of differentiable maps
• Generic projections
• Computing Roadmaps of General Semi-Algebraic Sets
• Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
• Le rôle des structures de données dans les problèmes d'élimination
• Computing roadmaps of semi-algebraic sets on a variety
• The Arithmetical Invariants of Algebraic Loci
• Algorithms in real algebraic geometry
• A Gröbner free alternative for polynomial system solving
• The theorem of Mather on generic projections for singular varieties
• Polar varieties and efficient real elimination