Description of the connected components of a semi-algebraic set in single exponential time. (Description des composantes connexes d’un ensemble semialgébrique en temps simplement exponentiel.) (French) Zbl 0764.14024

This paper is devoted to the presentation of a new algorithm computing the connected components of a semialgebraic set \(S\) in \(\mathbb R^ n\) with \(D^{n^{O(1)}}\) arithmetic operations in the base coefficient ring of \(S\) (this bound becomes \((n\log_ 2D)^{O(1)}\) if parallel time regarded), where \(D\) is the sum of the total degrees of the polynomials appearing in the description of \(S\). Moreover the total degrees of the polynomials appearing in the description of the connected components are well bounded. The main idea is to use a parametrized version of the celebrated roadmap algorithm for the effective computation of a semialgebraic path between two points of the same connected component of a semialgebraic set. The description of the connected components of \(S\) is obtained by applying such algorithm to two generic points in \(S\) and performing quantifier elimination over some well-precised formulae arising in the generic roadmap part of the algorithm. The good bounds of the resulting algorithm are due to the previous results of the authors concerning algorithms to compute roadmaps [the authors, cf. Applied algebra, algebraic algorithms and error-correcting codes, Proc. 8th Int. Conf., AAECC-8, Tokyo 1990, Lect. Notes Comput. Sci. 508, 180–196 (1991; Zbl 0764.14023) and Proc. Meeting devoted to S. Abhyankar (1990)] and algorithms to perform quantifier elimination [Bull. Soc. Math. Fr. 118, No. 1, 101–126 (1990; Zbl 0767.03017)].
The paper is clearly written, and gives a general vision of the algorithm without needing a comprehensive knowledge of the auxiliary algorithms previously mentioned. This work is to be added to the recent advances in computational real algebraic geometry concerning the search of algorithms with admissible complexity bounds.
Reviewer: J.M.Ruiz (Madrid)


14Q20 Effectivity, complexity and computational aspects of algebraic geometry
14P10 Semialgebraic sets and related spaces
68Q25 Analysis of algorithms and problem complexity
03C10 Quantifier elimination, model completeness, and related topics