Algebraic computations and applications to geometry (abstract only)

Real algebraic numbers are the real numbers that are real roots of univariate polynomials with integer coefficients. We study exact algorithms, from a theoretical and an implementation point of view, based on integer arithmetic of arbitrary precision, for computations with real algebraic numbers and applications of these algorithms on problems and algorithms in non linear computational geometry. In order to construct a real algebraic number we must compute the real roots of a univariate polynomial with integer cofficients. We unify and simplify the theory behind the subdivision based algorithms for real root isolation and we improve the complexity of the algorithm that is based on the continued fraction expansion of the real numbers. The best known complexity bound up today is achieved using new techniques. Moreover, we prove that the bound holds for non square-free polynomials and that in the same complexity bound we can compute the multiplicities of the real roots. We prove a new bound for the expected complexity of the algorithm based on continued fractions. We generalize the real root isolation algorithms to bivariate polynomial systems. Our experimental analysis proves the effectiveness of our methods. The algorithms that we consider for computations with real algebraic numbers are construction, comparison, sign evaluation and quantifier elimination. If the degree of the polynomial is small, i.e. ≤ 4 in the univariate case and ≤ 2 in the bivariate case, we propose special purpose algorithms that have constant arithmetic complexity. For all the algorithms we present a C++ implementation and an experimental analysis. In computational geometry we study the predicates needed by the algorithms for the arrangement of elliptic arcs in the plane and the computation of the Voronoi diagram of ellipses, also in the plane. Finally, given a convex lattice polygon we study algorithms for decomposing it to two other convex lattice polygons, such that their Minkowski sum is the original polygon.