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.