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

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

• 批准号: 1526335
• 负责人: Victor Milenkovic
• 金额: $ 25万
• 依托单位: University of Miami
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526335&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描述了一个舍入算法，该算法将输入特征投影到附近的包装特征。为了处理曲面的相交，该项目为另一种类型的封装创建了输出敏感算法，这种封装是一种隔离的封装，可以有遥远的边界顶点，但不能封装其他特征。封装只是解决方案的一部分，因此该项目还探索了通过避免退化（零）表达式的数值计算来使用有界复杂度算法计算拓扑结构的方法。 它研究了用图论分析显式表达式和代数技术分析涉及多项式根的表达式，其结果是包括一个软件库，用于实现具有自动形状舍入的计算几何算法。 该项目通过引入计算几何课程整合了教育和研究，在该课程中，使用图书馆教授和实施标准算法。 以前，多步算法的计算成本迫使学生孤立地考虑每个算法。