Combinatorial Algorithms in Real Algebraic Geometry

该项目继续研究离散几何和计算几何，为实代数几何中的算法研究开发新的组合思想。所研究的算法包括实数的存在理论、实闭域上的量词消去和构造任意半代数集的路线图。一个重要的发展来自于考虑这样一种情况，在这种情况下，这些问题存在于比环境空间的维度低的代数类型的维度上。在这种情况下，已经可以找到其组合复杂性取决于多样性的维度而不是环境空间的维度的算法和结构界限。这些思想将被用来：(1)开发更有效的算法来计算半代数集的连通分支的半代数描述。(2)研究了半代数集的Whitney分层的复杂性。(3)开发更有效的算法来计算半代数集的实数维。(4)研究其他复杂性参数，如输入几项式的界(输入单项的个数)，并探索将输入函数的类扩展到Pfaffian函数。(5)去掉Sharir最近的突破性结果中的通用性假设，它给出了一族超曲面(或这类曲面的曲面片)在一般位置上的下包络的复杂性的近乎尖锐的界。(6)研究经典区域定理是否可以进一步推广到代数集族中的代数簇的复杂性的界。这些问题的解决将对运动规划和计算机代数中的问题产生重大影响。

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.