AF:Small:Collaborative Research:Making Computational Geometry Polynomial in Derivation Length and in Dimension

计算几何是一门创建算法来设计和操作形状的学科。它在科学、工程和工业中有着广泛的应用——CAD/CAM系统就是一个显著的例子。问题是，当我们看到形状和它们的空间关系时，计算机只能看到数字——通常，为了速度，只能看到近似的“浮点数”。例如，用数字坐标表示的直线上的点，当四舍五入到计算机存储的位数时，可能不再位于任何公共线上。随后的计算依赖于一条直线或两条线最多相交一次，这可能会导致严重的错误。数值计算中的误差有时会受到舍入的限制，但对于三维形状的舍入没有实用的技术。这个项目通过封装来研究形状的舍入：用浮点顶点坐标将高复杂度的形状封装在近似多面体中。给定一个封装，pi描述了一个舍入算法，该算法将输入特征投影到附近的封装特征上。为了处理曲面的相交，该项目为另一种类型的封装创建了输出敏感算法，这是一种隔离封装，可以有遥远的边界顶点，但不能包含其他特征。封装只是解决方案的一部分，因此该项目还探索使用有界复杂度算法来计算拓扑结构，从而避免对退化（零）表达式进行数值计算。它研究使用图论来分析显式表达式和代数技术来分析涉及多项式根的表达式。其结果是包括一个软件库，用于实现具有自动形状舍入的计算几何算法。该项目通过介绍计算几何课程整合了教育和研究，其中使用图书馆教授和实施标准算法。以前，多步算法的计算成本迫使学生孤立地考虑每个算法。

Computational geometry is the discipline that creates algorithms todesign and manipulate shapes. It has wide application in science,engineering, and industry -- CAD/CAM systems are a notable example.The problem is, where we see shapes and their spatial relations, thecomputer sees only numbers -- and usually, for speed, onlyapproximate, "floating-point" numbers. E.g., points on a line thatare represented as numerical coordinates, when rounded to thenumber of digits the computer stores, may no longer lie on any commonline. Subsequent calculations that rely on a line being straight ortwo lines intersecting at most once can then go badly astray. Errorin numerical computation can sometimes be limited by rounding, butthere is no practical technique for rounding three-dimensional shapes.This project investigates shape rounding by encasement:High-complexity shapes are encased in approximating polyhedra withfloating-point vertex coordinates. Given an encasement, the PIs havedescribed a rounding algorithm that projects input features to nearbyencasement features. For dealing with intersections of surfaces, theproject creates output-sensitive algorithms for another type ofencasement, an isolating encasement that can have distant boundaryvertices but cannot encase other features.Encasement is only part of the solution, so the project also exploresways to compute topological structure using bounded-complexityarithmetic by avoiding numerical computation for the degenerate (zero)expressions. It investigates using graph theory to analyze explicitexpressions and algebraic techniques to analyze expressions involvingroots of polynomials.The outcome is to include a software library for implementingcomputational geometry algorithms with automated shape rounding. Theproject integrates education and research through an introductorycomputational geometry course in which standard algorithms are taughtand implemented using the library. Previously, the computational costof multi-step algorithms forced students to consider each algorithm inisolation.