A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets

DOI10.1145/2996450MaRDI QIDQ3177875zbMATH OpenOpenAlexFDO

Authors Éric Schost, Mohab Safey El Din

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.7836

zbMATH Keywords

algorithmscomplexityreal algebraic geometrysymbolic computationconnectivity queriesnonlinear computational geometry

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Real algebraic sets (14P05)

Abstract: A roadmap for a semi-algebraic set $S$ is a curve which has a non-empty and connected intersection with all connected components of $S$. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in higher-level algorithms. In this paper, we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets. Its output size and running time are polynomial in $(nD{)}^{nlog(d)}$, where $D$ is the maximum of the degrees of the input polynomials, $d$ is the dimension of the set under consideration and $n$ is the number of variables. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under our assumptions, it is the first roadmap algorithm with output size and running time polynomial in $(nD{)}^{nlog(d)}$.

Recommendations

• Algorithm for Connectivity Queries on Real Algebraic Curves
• Complexity of deciding connectivity in real algebraic sets
• Upper bounds on algebraic connectivity via convex optimization
• Determination of the connected components of a semialgebraic set in subexponential time
• Finding connected components of a semialgebraic set in subexponential time
• Finding connected components of a semialgebraic set in subexponential time
• Computing tight upper bounds on the algebraic connectivity of certain graphs
• scientific article; zbMATH DE number 21309
• \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
• Approximation algorithms for connected dominating sets

Cited in

(34)

• Solving determinantal systems using homotopy techniques
• \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
• Foreword
• Complexity of deciding connectivity in real algebraic sets
• Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems
• Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
• Solving parametric systems of polynomial equations over the reals through Hermite matrices
• Bit complexity for computing one point in each connected component of a smooth real algebraic set
• Improved complexity bounds for counting points on hyperelliptic curves
• Solving rank-constrained semidefinite programs in exact arithmetic
• scientific article; zbMATH DE number 27176 (Why is no real title available?)
• On types of isolated KKT points in polynomial optimization
• Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• On exact Reznick, Hilbert-Artin and Putinar's representations
• Computing critical points for invariant algebraic systems
• A geometric approach for analyzing parametric biological systems by exploiting block triangular structure
• Symmetric matrices whose entries are linear functions
• Refined F5 Algorithms for Ideals of Minors of Square Matrices
• Real root finding for determinants of linear matrices
• Construction of roadmaps in semi-algebraic sets
• Computing real radicals and \(S\)-radicals of polynomial systems
• Algorithm for Connectivity Queries on Real Algebraic Curves
• Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
• On types of degenerate critical points of real polynomial functions
• Numerical roadmap of smooth bounded real algebraic surface
• Exact algorithms for linear matrix inequalities
• Computing real witness points of positive dimensional polynomial systems
• A note on polynomial solvability of the CDT problem
• Fast Algorithms for Discrete Differential Equations
• Real root finding for low rank linear matrices
• Faster one block quantifier elimination for regular polynomial systems of equations
• Computing roadmaps in smooth real algebraic sets
• Homotopy techniques for solving sparse column support determinantal polynomial systems

This page was built for publication: A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177875)