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

AF：小：协作研究：使计算几何多项式在导数长度和维度上

• 批准号: 1524455
• 负责人: Elisha Sacks
• 金额: $ 25万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1524455&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Making

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.

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