The Design and Analysis of Geometric Algorithms

该项目研究了计算几何的三个广泛领域中的问题：(1)高效和健壮的几何基元的设计和实现，(2)多维搜索的算法复杂性，以及(3)用于随机(和去随机)几何算法的数学工具(例如，偏差理论)。这些领域涵盖了从实施和调试几何算法时出现的实际考虑到算法设计中出现的理论问题和下限证明。人们还在继续开发工具，这些工具最终可以用来生产和共享几何软件。

The project investigates problems within three broad areas of computational geometry: (1) design and implementation of efficient and robust geometric primitives, (2) algorithmic complexity of multidimensional searching and (3) mathematical tools (e.g. discrepancy theory) for randomized (and derandomized) geometric algorithms. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. Tools continue to be built which can ultimately be used to produce and share geometric software.