Structure-Sensitive Geometric Algorithms and Data Structures

结构敏感的几何算法和数据结构

• 批准号: 0098151
• 负责人: David Mount
• 金额: $ 25.5万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098151&HistoricalAwards=false
• 关键词: Structure; Sensitive; Geometric; Algorithms; Data

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.

建议#0098151山，大卫大学的马里兰州，大学公园计算几何的生命力在很大程度上取决于它的相关性，以现实世界的问题和应用。 该领域对这些领域做出了重大贡献，但持续的成功需要了解典型应用中出现的问题中存在的约束和结构。 传统的最坏情况下的渐近分析往往是过于生硬的工具，建立几何算法的效率，因为几何数据集往往包含简化结构，最坏情况下有效的算法可能会忽略。 另一个原因是，最坏情况的分析可能会导致设计人员专注于困难的数据配置，在实践中很少出现。 因此，许多几何软件的设计者不把计算几何作为算法的相关来源，而是依赖于性能未经证实的几何学，本研究的目标是通过开发在实践中有效且其效率可正式证明的几何问题的算法和数据结构来对抗这种看法。 我们实现实际效率的方法是通过对简化结构存在的敏感性。 对于大多数算法，该结构可以存在于输入中。 对于数据结构，这种结构存在于查询的分布中。 我们的目标是设计和分析算法和数据结构，当这种简化结构存在时，它们是最有效的。 在没有这种结构的情况下，这些算法将理想地退化为最佳最差情况算法。 这种方法将被应用于几何问题的信息检索（多维最近邻搜索和点定位）模式识别，强大的统计，并在聚类。