Divide and conquer roadmap for algebraic sets

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

m a t h c a l A

are bounded by

d^{O (k)}

. As an application of our result we prove that for any real algebraic subset

V

of

m a t h b b 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^{l o g (k)} d)^{O (k l o g (k))}

, consisting of at most

(k^{l o g (k)} d)^{O (k l o g (k))}

curve segments of degrees bounded by

(k^{l o g (k)} d)^{O (k l o g (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.

Review text

In this paper, the authors deal with the following algorithmic problems: {\parindent=6mm \begin{itemize}\item[(1)] determining the number of semi-algebraically connected components of the set of zeroes of a multivariate polynomial in a real closed field; \item[(2)] decide whether two points belong to the same semi-algebraically connected component of this set; \item[(3)] if so, to compute a semi-algebraic path with image contained in this set. \end{itemize}} The main results of this paper are the following: Given and ordered subdomain \(D\) of a real closed field \(R\), there exists an algorithm that takes as input {\parindent=6mm \begin{itemize}\item[(1)] a polynomial \(P\in D[X_1,\dots, X_k]\), with \(\deg(P)\leq d\); \item[(2)] a finite set \({\mathcal A}=\{p_1,\dots, p_m\}\) contained in the ``real variety \(V\) defined by the zeroes of \(P\) in \(R^k\), such that for each \(i=1,\dots, m\), the degree of a ``real univariate representation (a specific algebraic way of representing these points with coefficients in \(D\)) of \(p_i\) is bounded by \(D_i\); \end{itemize}} and computes the following outputs: {\parindent=6mm \begin{itemize}\item[(1)] a ``roadmap (a semi-algebraic set of \(V\) of dimension at most one with some extra conditions) of \(V\) containing \({\mathcal A}\). \item[(2)] the number of semi-algebraically connected components of \(V\). \end{itemize}} The complexity of computing the first output is bounded by \[ \left(1+\sum_{i=1}^mD_i^{{\mathcal O}(\log^2k)}\right)\big(k^{\log k}d\big)^{{\mathcal O}(k\log^2k)}, \] while the size of the output is bounded by \(\big(\#{\mathcal A}+1\big)(k^{\log\,k}d)^{{\mathcal O}(k\,\log k)}\), and the degrees of the polynomials appearing in the descriptions of it are bounded by \(\big(\max_{1\leq i\leq m}D_i\big)^{{\mathcal O}(\log k)}\big(k^{\log k}d\big)^{{\mathcal O}(k\,\log k)}\). The complexity of computing the second output is bounded by \(\big(k^{\log k}d\big)^{{\mathcal O}(k\,\log^2 k)}\). If in addition we are given with the input two real univariate representations whose associated points are contained in \(V\) with degrees bounded by \(D_1\) and \(D_2\) respectively, there is an algorithm deciding whether the two points belong to the same semi-algebraically connected component of \(V\), and if so computes a description of a semi-algebraic path connecting them with image contained in \(V\). The complexity of this algorithm is bounded by \[ \left(D_1^{{\mathcal O}(\log^2k)}+D_2^{{\mathcal O}(\log^2k)}+1\right)\big(k^{\log k}d\big)^{{\mathcal O}(k \log^2k)}, \] and the size the the output as well as the degrees of the polynomials appearing in the descriptions of the curve segments and points are bounded by \(\max\{1,D_1,D_2\}^{{\mathcal O}(\log k)}\big(k^{\log k}d\big)^{{\mathcal O}(k \log k)}\). All these bounds above improve the previous known estimations, some of them gotten by the authors and some collaborators in [\textit{S. Basu} et al., Found. Comput. Math. 14, No. 6, 1117--1172 (2014; Zbl 1322.14090)]. In addition, as an application of the results above, the author prove the following result which was already addressed in [\textit{D. D'Acunto} and \textit{K. Kurdyka}, Bull. Lond. Math. Soc. 38, No. 6, 951--965 (2006; Zbl 1106.14046)] without upper bounds on complexity: if \(V\) is a real algebraic variety defined by a polynomial of degree at most \(D\), and \(C\) a connected component of \(V\) contained in the unit ball centered at the origin, any two points \(x, y\in C\) can be connected inside \(C\) by a semi-algebraic path of length at most \(\big(k^{\log k}d\big)^{{\mathcal O}(k \log k)}\), consisting of at most \(\big(k^{\log k}d\big)^{{\mathcal O}(k \log k)}\)curve segments of degrees bounded by \(\big(k^{\log k}d\big)^{{\mathcal O}(k \log k)}\).

Recommendations

Cites work

Cited in

(23)

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)