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.