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

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.