4 papers
Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
Jérémy Berthomieu, Edern Gillot, Mohab Safey El Din
We consider the problem of computing sample points in each connected component of a semi-algebraic set defined by the non-vanishing or the positivity of an n-variate polynomial of…
Refined bit complexity for the computation of at least one point per connected component of a smooth complete intersection real algebraic set
Jesse Elliott, Mark Giesbrecht, Edern Gillot +2
We refine the bit complexity analysis of an algorithm for the computation of at least one point per connected component of a smooth real algebraic set, yielding exponential speedup…
Algebraic Proofs of Path Disconnectedness using Time-Dependent Barrier Functions
Didier Henrion, Jared Miller, Mohab Safey El Din
Two subsets of a given set are path-disconnected if they lie in different connected components of the larger set. Verification of path-disconnectedness is essential in proving the…
Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity
Rémi Prébet, Mohab Safey El Din, Éric Schost
A roadmap for an algebraic set defined by polynomials with coefficients in the field of rational numbers is an algebraic curve contained in whose intersection…