This project continues research in discrete and computational geometry, developing new combinatorial ideas for the study of algorithms in real algebraic geometry. The algorithm studied include the existential theory of the reals, quantifier elimination over real closed fields and constructing roadmaps of arbitrary semi-algebraic sets. An important development comes from considering the situation in which these problems live on an algebraic variety of dimension lower than the dimension of the ambient space. In this situation it has been possible to find algorithms and structural bounds for which the combinatorial complexity depends on the dimension of the variety rather than on the dimension of the ambient space. These ideas will be used to: (1) Develop more efficient algorithms to compute a semi- algebraic description of the connected components of a semi- algebraic set. (2) Investigate the complexity of a Whitney stratification of a semi-algebraic set. (3) Develop more efficient algorithms to compute the real dimension of a semi-algebraic set. (4) Investigate other parameters of complexity such as the input fewnomial bound (the number of input monomials) and explore broadening the class of input functions to Pfaffian functions. (5) Remove the genericity hypotheses in the recent breakthrough result of Sharir, which gives nearly sharp bounds on the complexity of the lower envelope of a family of hypersurfaces (or patches of such surfaces) in general position. (6) Investigate whether the classical zone theorem can be further extended to bound the complexity of an algebraic variety in the midst of a family of algebraic sets. The solution of these problems would have significant impact on problems in motion planning and computer algebra.
