Structure-Sensitive Geometric Algorithms and Data Structures

提案#0098151，马里兰大学戴维德分校，学院公园计算几何的生命力在很大程度上取决于它与现实世界问题和应用程序的相关性。这一领域对这些领域作出了重大贡献，但要想取得持续的成功，就需要了解在典型应用中出现的问题中存在的制约因素和结构。传统的最坏情况下的渐近分析对于建立几何算法的效率来说往往过于迟钝，因为几何数据集通常包含简化的结构，而最坏情况下的高效算法可能会忽略这一点。另一个原因是，最坏的情况分析可能会导致设计人员专注于实际中很少出现的困难数据配置。因此，许多几何软件的设计者不把计算几何作为算法的相关来源，而是依赖于性能未经证明的启发式算法。本研究的目标是通过开发在实践中高效且其效率是形式上可证明的几何问题的算法和数据结构来对抗这种看法。我们实现实际效率的方法是通过对存在简化结构的敏感性。对于大多数算法，这种结构可能存在于输入中。对于数据结构，该结构存在于查询的分布中。我们的目标是设计和分析在存在这种简化结构时最高效的算法和数据结构。在缺乏这种结构的情况下，理想情况下，这些算法将降级为最好的最坏情况算法。这种方法将应用于信息检索(多维最近邻搜索和点定位)模式识别、稳健统计和聚类中的几何问题。

Proposal #0098151Mount, DavidU of Maryland, College ParkThe vitality of computational geometry depends heavily on its relevance to real-world problems and applications. This field has made significant contributions to these areas, but continued success requires an understanding of the constraints and structure present in the problems that arise in typical applications. Traditional worst-case asymptotic analysis is often too blunt a tool for establishing the efficiency of geometric algorithms, since geometric data sets often contain simplifying structure, which worst-case efficient algorithms may ignore. Another reason is that worst-case analyses may lead designers to concentrate on difficult data configurations that arise only rarely in practice. As a result, many designers of geometric software do not look to computational geometry as a relevant source of algorithms, and instead rely on heuristics of unproven performance.The goal of this research is counter this perception by developing ad implementing algorithms and data structures for geometric problems that are both efficient in practice and whose efficiency is formally provable. Our approach in achieving practical efficiency is through a sensitivity to presence of simplifying structure. For most algorithms this structure may be present in the input. For data structures this structure is present in the distribution of the queries. Our goal is to design and analyze algorithms and data structures that are most efficient when this simplifying structure is present. In the absence of this structure, these algorithms would ideally degrade to the best worst-case algorithms. This approach will be applied to geometric problems in information retrieval (multidimensional nearest neighbor searching and point location) pattern recognition, robust statistics, and in clustering.