AF: Small: Degree-Driven Design of Geometric Algorithms

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

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.