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

计算几何是理论计算机科学的分支，致力于几何算法和数据结构的设计、分析和实现。几何是无处不在的：几何问题自然地出现在任何模拟物理世界或与物理世界交互的计算领域。计划中的研究集中在数据聚类的基本问题上，采取几何的观点来看待这一问题。该项目将研究什么是数据聚类所需且充分的几何条件，以及如何快速检查这些条件，并对数据进行聚类。本项目要研究的问题包括：(I)使用几个“中心”(其中一个中心可以是几个点)或高维空间，如直线(即，射影聚类)对数据进行聚类(即遍历)的充分条件。(2)接近集群所需的中心数量，并努力提高所需的集群数量。(3)覆盖面问题--数据能否由几块/几个柱面/等覆盖？能否高效、快速地计算出这样的覆盖率？(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.