Properness defects and projections and computation of at least one point in each connected component of a real algebraic set (Q705131)

Finding at least one point in each connected component of a semi-algebraic set, or at least deciding if it is empty, is a fundamental problem in effective real algebraic geometry, which appears in many academic or industrial applications as for instance in robotics or celestial mechanics. A well known algorithm having such an output is the method of cylindrical algebraic decomposition presented by \textit{G. E. Collins} [``Quantifier elimination for real closed fields by cylindrical algebraic decomposition'', in: Automata theory and formal languages, Lect. Not. Comput. Sci. 33, 515--532]. However it has complexity doubly exponential in the number of variables, in terms of arithmetic operations and size of the output. More recently, alternative algorithms were proposed by \textit{S. Basu, R. Pollack} and \textit{M.-F. Roy} [J. ACM 43, No. 6, 1002--1045 (1996; Zbl 0885.68070)], and by \textit{J. Heintz, M.-F. Roy} and \textit{P. Solerno} [Comput. J. 36, No. 5, 427--431 (1993; Zbl 0780.68058)]. This question is reduced to the computation of at least one point in each connected component of several real algebraic sets. This paper is in keeping with this framework. Many of the previous methods presented deal with the problem by means of projections requiring a hypothesis of properness. In this article, the authors propose a new algorithm which avoids this hypothesis. More precisely, they show how studying the set of non-properness of a linear projection \(\Pi\) enables to detect the connected components of a real algebraic set without critical points for \(\Pi\). The algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. The experiments show the efficiency on a family of examples.