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

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

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.