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

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

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.