NSF-BSF: AF: Small: New directions in geometric traversal theory

NSF-BSF：AF：小：几何遍历理论的新方向

• 批准号: 2317241
• 负责人: Sariel Har-Peled
• 金额: $ 11万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2317241&HistoricalAwards=false
• 关键词: NSF; BSF; AF; Small; New

Computational geometry is the branch of theoretical computer science devoted to the design, analysis, and implementation of geometric algorithms and data structures. Geometry is omnipresent: geometric problems arise naturally in any computational field that simulates or interacts with the physical world. The planned research focuses on the fundamental problem of clustering data by taking a geometric viewpoint of the problem. The project will study what are the geometric conditions that are required and sufficient to cluster the data, and how to quickly check for these conditions, and cluster the data.The problems to be studied in this project include: (i) sufficient conditions for data to be clustered (i.e., traversed) using a few "centers", where a center is either several points, or higher dimensional spaces such as lines (i.e., projective clustering). (ii) Approximating the number of centers needed to cluster, and trying to improve the number of clusters needed. (iii) Coverage problems – can the data be covered by a few slabs/cylinders/etc.? Can such cover be computed efficiently and quickly? (iv) Finding a small subset of the data that can be clustered instead of the whole point set and, importantly, providing a proof that no better clustering is possible with fewer centers. The project aims to develop algorithms to compute such sets efficiently.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

计算几何形状是理论计算机科学的分支，该分支致力于几何算法和数据结构的设计，分析和实施。几何是无所不在的：几何问题自然出现在模拟或与物理世界相互作用的任何计算领域中。计划研究的重点是通过采用该问题的几何观点来群集数据的基本问题。 The project will study what are the geometric conditions that are required and sufficient to cluster the data, and how to quickly check for these conditions, and cluster the data.The problems to be studied in this project include: (i) sufficient conditions for data to be clustered (i.e., traversed) using a few "centers", where a center is either several points, or higher dimensional spaces such as lines (i.e., projective clustering). （ii）近似聚类所需的中心数，并试图改善所需的簇数。 （iii）覆盖范围问题 - 数据可以由几个平板/气缸/等覆盖吗？可以有效，快速计算此类覆盖物吗？ （iv）找到一小部分数据子集可以聚集，而不是整个点集，并且重要的是提供一个证据表明，在中心较少的情况下不可能进行更好的聚类。该项目旨在开发算法以有效地计算此类集合。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估来获得支持。