Combinatorial Algorithms in Real Algebraic Geometry

这个项目继续在离散和计算几何的研究，发展新的组合思想的研究算法在真实的代数几何。研究的算法包括实数的存在性理论、真实的闭域上的量词消去和任意半代数集的路线图的构造。 一个重要的发展来自考虑的情况下，这些问题生活在一个代数品种的尺寸低于周围空间的尺寸。 在这种情况下，已经有可能找到算法和结构界限，其组合复杂性取决于多样性的维度，而不是周围空间的维度。 这些想法将用于： (1)开发更有效的算法来计算半- 半连通分支的代数描述 代数集 (2)调查的复杂性惠特尼分层的一个 半代数集 (3)开发更有效的算法来计算真实的 半代数集的维数 (4)研究其他复杂性参数，例如 输入多项式界（输入单项式的个数）， 探索将输入函数类扩展到Pfweian 功能协调发展的 (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.