AF: Small: Degree-Driven Design of Geometric Algorithms

点击翻译按钮获取中文摘要

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.