AF: Small: Geometric Clustering and Covering: New Directions

University Of Iowa, Iowa City IA

Investigators

Abstract

Clustering, which collects nearby data together in groups, is a key operation in data analysis, but one whose computation is surprisingly difficult due to the many choices for dividing data into groups. This project investigates some fundamental algorithmic problems and new directions in the areas of geometric clustering and covering. Progress on the problems considered in this project will not only enhance knowledge in the PI's core research field, and that of his graduate students, but also yield new techniques, ideas, and points of view that will be useful beyond the core area. One avenue for such impact is the training of graduate students who will work on this project. By the time they successfully complete their dissertations, these students develop a deep understanding of how technical knowledge may (or may not) influence real world problem solving, an appreciation for the difficulty of obtaining reliable new knowledge, and a sense of the excitement of the process of discovery. This experience informs their work, whether they end up in academia or industry. In geometric clustering, the goal is to partition data, viewed as a set of points, into groups based on similarity. Geometric clustering can help infer useful patterns from data, but can also help in planning infrastructure installation, such as base station placement in a cellular network. In geometric covering, we wish to cover a set of points by the smallest possible number of a given set of objects; such problems arise in the context of sensor networks. The clustering and covering problems studied in this project are viewed as optimization problems. These problems are typically NP-complete, which essentially means that it is not possible to solve them exactly using an algorithm with guaranteed efficiency. The PI will examine efficient algorithms that solve the problems approximately, and study the best approximation that can be provably guaranteed. The PI expects that the project will contribute exciting new ideas and techniques at the intersection of the fields of Approximation Algorithms and Computational Geometry.