AF: Small: Degree-Driven Design of Geometric Algorithms

AF：小：几何算法的度驱动设计

• 批准号: 1018498
• 负责人: Kevin Jeffay
• 金额: $ 41.86万
• 依托单位: University of North Carolina at Chapel Hill
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018498&HistoricalAwards=false
• 关键词: AF; Small; Degree; Driven; Design

Algorithms and software for geometric problems are usually designed and implemented in several layers of abstraction: For example, a map in a GPS navigation unit may be represented as a road network topology (just the interconnections) on top of the road geometry (a collection of line segments), which is represented with coordinates (as a sequence of points in a standard geodesic coordinate system), which are stored as numbers in a computer memory (which have a relatively small number of bits). At times, assumptions at higher levels of abstraction (e.g., lines are continuous, straight, and infinitely thin) are broken by the realities of the underlying levels (e.g., most points fall off a line when rounded to "machine precision"). Examples can be found in geometric algorithms for motion capture, robot simulation, x-ray crystallography, video tracking, and many other applications.Sophisticated implementers of geometric algorithms will identify exactly what properties one level needs from its underlying levels, and carefully implement the underlying levels to provide these. The increasing amounts of geometric data mean that most implementers do not have sophistication in geometric algorithms, either because they are more focused on the sophisticated knowledge of their own domain, or because they are students who have not yet reached that level of sophistication.Computer Scientists are accustomed to designing algorithms to optimize running time and memory space -- two resources that are limited, but whose limits may not be known in advance. This project adds arithmetic precision to this list of resources. This resource can be measured, up to constants, by the degree of polynomials in predicates and constructions. Restricting designers to low degree predicates forces creative new solutions to standard problems that can be guaranteed correct in machine precision. The result will be a codebook of algorithms that have been developed and tested by graduate and undergraduate students in this project, and can be the basis for robust primitives or further exploration in education and practical settings.

几何问题的算法和软件通常在几个抽象层中设计和实现：例如，GPS导航单元中的地图可以表示为道路网络拓扑（仅是互连）在道路几何图形之上（线段的集合），用坐标表示（作为标准测地坐标系中的点的序列），其作为数字存储在计算机存储器中（其具有相对少量的比特）。 有时，更高抽象级别的假设（例如，线是连续的、直的，并且无限细）被底层的现实（例如，当四舍五入到“机器精度”时，大多数点偏离直线）。 运动捕捉、机器人模拟、X射线晶体学、视频跟踪和许多其他应用的几何算法中都可以找到示例。几何算法的复杂实现者将准确识别一个级别需要其底层级别的哪些属性，并仔细实现底层级别来提供这些。 几何数据量的不断增加意味着大多数实现者在几何算法方面并不成熟，这要么是因为他们更专注于自己领域的复杂知识，要么是因为他们是尚未达到那种复杂程度的学生。计算机科学家习惯于设计优化运行时间和内存空间的算法-这两种资源是有限的，但是其极限可能事先不知道。 此项目将算术精度添加到此资源列表中。 这种资源可以通过谓词和结构中多项式的次数来测量，直到常数。 限制设计师到低程度的谓词迫使创造性的新的解决方案，可以保证正确的机器精度的标准问题。 其结果将是一个由研究生和本科生在本项目中开发和测试的算法码本，可以作为强大的原语或在教育和实际环境中进一步探索的基础。