This award addresses geometric optimization problems from three areas: shape fitting, image segmentation, and geometric versions of combinatorial optimization problems like set cover. The PIs will examine new problems that have been unearthed by recent work, and will also attack some old problems that have thus far eluded satisfactory solutions.
The shape fitting problem is one of finding the best shape that fits a given set of points from an implicitly given family of shapes. A well known example is: given a set of points in the plane, find the best line that fits them. The PIs will examine questions connected with the development of approximation algorithms for such problems with near-linear running time. In a typical instance of the geometric set cover problem, we are given a set of points and a set of disks in the plane, and we wish to find the smallest subset of the disks that covers all the points. In this example, we want to cover with disks, but in other instances we want to cover with triangles, rectangles, or some other shape. Such algorithmic problems are typically NP-hard, and the PIs aim to develop improved approximation algorithms. One approach to the image segmentation problem views the image as a weighted graph and seeks to find the subset of nodes in the graph with maximum weight, subject to a shape constraint such as one that requires the subset to be ``star-shaped''. Here the PIs are interested in exact algorithms with polynomial running time.
Consider the problems of (a) clustering or identifying the linear trend in data; (b) cheapest placement of sensors to monitor a given region; and (c) automatically identifying the lung portion of a medical image of a lung. The research that this award supports views computer programs for these problems as algorithms for geometric optimization, where we want to maximize a certain quantity subject to several constraints. The research investigates the existence of fast algorithms for such optimization problems. Progress on the problems studied will enhance core knowledge within Computational Geometry, and expand the reach of a graph theoretic approach to medical image analysis.
The proposed work is a rich training ground for PhD students who will be exposed not only to theoretical computational geometry but also to some of its applications. The students will also be enriched in a broader way by graduate courses on approximation algorithms, computational geometry, and applications.
