Algorithms in semi-algebraic geometry.

摘要

In this thesis we present new algorithms to solve several very general problems of semi-algebraic geometry. These are currently the best algorithms for solving these problems. In addition, we have proved new bounds on the topological complexity of real semi-algebraic sets, in terms of the parameters of the polynomial system defining them, which improve some old and widely used results in this field.;In the first part of the thesis we describe new algorithms for solving the decision problem for the first order theory of real closed fields and the more general problem of quantifier elimination. Moreover, we prove some purely mathematical theorems on the number of connected components and on the existence of small rational points in a given semi-algebraic set.;The second part of this thesis deals with connectivity questions of semi-algebraic sets. We develop new techniques in order to give an algorithm for computing roadmaps of semi-algebraic sets.;In the third part of the thesis we extend and improve a classical and widely used result of Oleinik and Petrovsky, Thom and Milnor, bounding the sum of the Betti numbers of semi-algebraic sets. Using the ideas behind this result, we give the first singly exponential algorithm for computing the Euler characteristic of an arbitrary closed semi-algebraic set.;One common thread that links these results is that our bounds are separated into a combinatorial part (the part depending on the number of polynomials) and an algebraic part (the part depending on the degrees of the polynomials). The combinatorial part of the complexity of our algorithms is frequently tight and this marks the improvement of many of our results. This is most striking when one considers that in many applications, for instance in computational geometry, it is the number of polynomials which is the most important parameter.;Another important and new feature of some of our results is that when the given semi-algebraic set is contained in a lower dimensional variety, the combinatorial part of the complexity depends on the dimension of this variety rather than on the dimension of the ambient space and this is often useful in applications.