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.