Divide and conquer roadmap for algebraic sets

DOI10.1007/S00454-014-9610-9MaRDI QIDQ464736zbMATH OpenOpenAlexFDO

Authors Saugata Basu, Marie-Françoise Roy

Publication date 29 October 2014

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

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

zbMATH Keywords

complexityreal algebraic varietiesdivde and conquer algorithmreal univariate representationroadmaps

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Real algebraic sets (14P05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: Let $mathrmR$ be a real closed field, and $mathrmDsubsetmathrmR$ an ordered domain. We describe an algorithm that given as input a polynomial $PinmathrmD[X_1,ldots,X_k]$, and a finite set, $mathcalA=p_1,ldots,p_m$, of points contained in $V=mathrmZer(P,mathrm{R}^k)$ described by real univariate representations, computes a roadmap of $V$ containing $mathcalA$. The complexity of the algorithm, measured by the number of arithmetic operations in $mathrmD$ is bounded by $left(su{m}_{i=1}^m{D}_i^{O(lo{g}^2(k))}+1ight)(k^{log(k)}d{)}^{O(klo{g}^2(k))}$, where $d=mathrmdeg(P)$, and $D_i$ is the degree of the real univariate representation describing the point $p_i$. The best previous algorithm for this problem had complexity $mathrmcard(mathcalA{)}^{O(1)}{d}^{O(k^{3/2})}$ due to Basu, Roy, Safey-El-Din, and Schost (2012), where it is assumed that the degrees of the polynomials appearing in the representations of the points in $mathcalA$ are bounded by $d^{O(k)}$. As an application of our result we prove that for any real algebraic subset $V$ of $mathbb{R}^k$ defined by a polynomial of degree $d$, any connected component $C$ of $V$ contained in the unit ball, and any two points of $C$, there exist a semi-algebraic path connecting them in $C$, of length at most $(k^{log(k)}d{)}^{O(klog(k))}$, consisting of at most $(k^{log(k)}d{)}^{O(klog(k))}$ curve segments of degrees bounded by $(k^{log(k)}d{)}^{O(klog(k))}$. While it was known previously, by a result of D'Acunto and Kurdyka, that there always exists a path of length $(O(d){)}^{k-1}$ connecting two such points, there was no upper bound on the complexity of such a path.

Recommendations

• A baby step-giant step roadmap algorithm for general algebraic sets
• Computing Roadmaps of General Semi-Algebraic Sets
• scientific article; zbMATH DE number 177864
• Decomposing algebraic sets using Gröbner bases
• Computing roadmaps of semi-algebraic sets on a variety
• Algebraic separation and shadowing of arbitrary sets
• Construction of roadmaps in semi-algebraic sets
• scientific article; zbMATH DE number 1256732
• scientific article; zbMATH DE number 2086288

Cites work

• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 8550 (Why is no real title available?)
• scientific article; zbMATH DE number 17838 (Why is no real title available?)
• scientific article; zbMATH DE number 192849 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 589123 (Why is no real title available?)
• scientific article; zbMATH DE number 1849873 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• scientific article; zbMATH DE number 3053541 (Why is no real title available?)
• A baby step-giant step roadmap algorithm for general algebraic sets
• A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
• Algorithms in real algebraic geometry
• BOUNDS FOR GRADIENT TRAJECTORIES AND GEODESIC DIAMETER OF REAL ALGEBRAIC SETS
• Computing roadmaps of semi-algebraic sets on a variety
• Construction of roadmaps in semi-algebraic sets
• Counting connected components of a semialgebraic set in subexponential time
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Betti Numbers of Real Varieties
• On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
• Problems and theorems in analysis II. Theory of functions, zeros, polynomials, determinants, number theory, geometry. Transl. from the German by C. E. Billigheimer.

Cited in

(17)

• Quantitative curve selection lemma
• On computing a set of points meeting every cell defined by a family of polynomials on a variety
• scientific article; zbMATH DE number 27176 (Why is no real title available?)
• Topology of real multi-affine hypersurfaces and a homological stability property
• Bounding the length of gradient trajectories
• Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results
• On a generalization of Stickelberger's theorem
• A baby step-giant step roadmap algorithm for general algebraic sets
• Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
• scientific article; zbMATH DE number 797449 (Why is no real title available?)
• Algorithm for Connectivity Queries on Real Algebraic Curves
• Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
• Numerical roadmap of smooth bounded real algebraic surface
• Computing Roadmaps of General Semi-Algebraic Sets
• Computing roadmaps in smooth real algebraic sets
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• Quickly computing isotopy type for exponential sums over circuits (extended abstract)

This page was built for publication: Divide and conquer roadmap for algebraic sets

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