Divide and conquer roadmap for algebraic sets

DOI10.1007/S00454-014-9610-9zbMATH Open1329.14109arXiv1305.3211OpenAlexW1984254060MaRDI QIDQ464736FDOQ464736

Authors: Saugata Basu, Marie-Françoise Roy 

Publication date: 29 October 2014

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

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.

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

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

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)

Cites Work

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

Cited In (16)

• Quantitative curve selection lemma
• Title not available (Why is that?)
• 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
• Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
• A baby step-giant step roadmap algorithm for general algebraic sets
• Title not available (Why is that?)
• 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
• Quickly computing isotopy type for exponential sums over circuits (extended abstract)
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets

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)