Geometric Complexity Problems

计算几何一开始就承诺统一解决不同计算领域中出现的几何问题的多种努力，这些领域包括统计学、生物学、机器人运动规划、图形学、图像分析、虚拟现实和数据挖掘。在二十年的时间里，该领域已经产生了丰富的工具集来解决几何性质的算法问题。几何问题的设计和分析的一个反复出现的特征是所研究问题的计算和组合方面之间的紧密联系。理解问题背后的组合几何是找到有效解决方案的基础。这个项目将探索在几何背景下出现的组合问题，以开发新的工具，并改进现有的工具，用于设计和分析几何算法。主要目标是开发强大的组合工具，可以用来构建更简单和更有效的算法。分析这些算法的复杂性可能会有相当大的额外成本，但这一成本对最终用户是透明的。该项目还将研究技术，使其有可能获得对典型输入的几何算法行为的更现实的估计。例如，这可以通过识别一些能够捕捉数据集的“坏”的指标来实现。这样的衡量标准或许能够区分最坏的情况和“典型”的情况，并提供一个简单的先验估计，说明给定的计算程序处理特定类别输入的能力有多好。

Computational geometry began with the promise of unifying the multiplicity of efforts to solve geometric problems arising in diverse areas of computation such as statistics, biology, robot motion planning, graphics, image analysis, virtual reality, and data mining. In two decades, the field has produced a rich collection of tools for solving algorithmic problems of a geometric nature. A recurring feature in the design and analysis of geometric problems is the strong link between the computational and combinatorial aspects of the questions under investigation. Understanding the combinatorial geometry behind the problem is fundamental to being able to find an efficient solution. This project will explore combinatorial problems arising in geometric contexts in order to develop new tools and to refine tools already available for the design and analysis of geometric algorithms.The primary goal is to develop powerful combinatorial tools which can be utilized to construct simpler and more efficient algorithms. It may be that there is considerable additional cost to analyze the complexity of these algorithms but this cost will be transparent to the end user. The project will also investigate techniques that would make it possible to obtain more realistic estimates on the behavior of geometric algorithms on typical inputs. This might be accomplished, for example, by identifying some metrics that capture the "badness" of a data set. Such a metric might be able to distinguish worst-case situations from ``typical'' ones, and provide an easy a priori estimate of how well a given computational procedure can handle a specific class of inputs.