AF: Small: Numeric-Symbolic Techniques for Geometric Problems in Algebra and Analysis

所有精确数值算法都必须隐式地解决某种“零问题”，即判断在其计算过程中出现的各种定义良好的数字是否为零。无法确定零是许多应用中普遍存在的数值非鲁棒性的根本原因。PI通过引入“精确分辨率”算法避开了零问题。直观地说，它们可以解出任意给定参数的问题。这种方法最近的成功见于PI在运动规划方面的工作。在更多的技术细节中，该奖项研究三类问题的分辨率准确性：(A)计算3D多面体集的Voronoi图，或二维k-椭圆的Voronoi图，目前还没有“明确的”精确算法。(B)解析和调和根隔离，其中精确方法由于隐式零问题而失效。(C)显化问题，如计算一个好的标量函数的莫尔斯-斯莫尔复合体，以及协维数2的代数变化的同位素近似（例如，空间曲线）。处理分析问题的能力对理论计算机科学来说是一种新的能力。计算科学与工程中的许多问题都是在连续面上定义的，并且没有精确解；精确分辨率算法为它们提供了实用且理论上合理的算法。更广泛地说，这项工作有助于符号数值计算的新兴领域。PI的研究训练新一代的计算机科学学生使用新的工具来解决连续问题。

All exact numerical algorithms must implicitly solve some "Zero Problem", namely decide if various well-defined numbers arising in the course of its computation are actually zero. The inability to decide zero is the root cause of pervasive numerical nonrobustness in many applications. The PI side-steps the Zero Problem by introducing "resolution-exact" algorithms. Intuitively, they solve the problem up to any given epsilon parameter. Recent successes of this approach are seen in the PI's work in motion planning.In more technical detail, this award studies resolution-exactness to three classes of problems:(A) Computing the Voronoi diagrams of polyhedral sets in 3D, or of k-ellipses in 2D where no current "explicit" exact algorithms are known.(B) Analytic and harmonic root isolation, in which exact methods fail because of the implicit Zero Problem. (C) Explicitization Problems such as computing the Morse-Smale complex of a nice scalar function, and isotopic approximation of algebraic varieties of co-dimension 2 (e.g., spatial curves).The ability to treat analytic problems is new for Theoretical Computer Science. Many problems of Computational Science and Engineering are defined on the continua, and have no exact solutions; resolution-exact algorithms provide practical yet theoretically-sound algorithms for them. More broadly, this work contributes to the emerging area of symbolic-numeric computation. The PI's research trains a new generation of Computer Science students using new tools for attacking continua problems.