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.

计算几何是理论计算机科学的一个分支，致力于几何算法和数据结构的设计、分析和实现。几何学无所不在：几何问题自然出现在任何模拟物理世界或与物理世界交互的计算领域。该项目将从几何角度研究数据聚类的基本问题，研究聚类数据所需的充分几何条件，以及如何快速检查这些条件并对数据进行聚类。本项目要研究的问题包括： (i) 使用几个“中心”对数据进行聚类（即遍历）的充分条件，其中中心可以是几个点，也可以是更高维的空间，例如线（即，投影聚类）。需要聚类的中心数量，并尝试提高所需聚类的数量 (iii) 覆盖问题 – 数据是否可以被几个板/圆柱体/等覆盖？ (iv) 找到可以聚类的一小部分数据，而不是整个点集，重要的是，提供一个证明，证明更少的中心不可能实现更好的聚类。该项目旨在开发算法来有效地计算此类集合。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。