AF: Small: Some New and Old Frontiers in Geometric Optimization

该奖项从三个方面解决几何优化问题：形状拟合、图像分割和组合优化问题的几何版本，如集合覆盖。ppi将审查最近工作中发现的新问题，也将解决一些迄今尚未得到满意解决的老问题。形状拟合问题是从隐式给定的形状族中找到适合给定点集的最佳形状。一个众所周知的例子是：给定平面上的一组点，找到最适合它们的直线。pi将研究与近似算法的发展有关的问题，这些问题具有近似线性的运行时间。在几何集合覆盖问题的一个典型实例中，我们给定平面上的一组点和一组磁盘，我们希望找到覆盖所有点的磁盘的最小子集。在本例中，我们希望用磁盘覆盖，但在其他实例中，我们希望用三角形、矩形或其他形状覆盖。这样的算法问题通常是np困难的，而pi的目标是开发改进的近似算法。图像分割问题的一种方法将图像视为一个加权图，并寻求在图中找到具有最大权重的节点子集，并受到形状约束，例如要求子集为“星形”。在这里，pi对具有多项式运行时间的精确算法感兴趣。考虑以下问题：(a)聚类或识别数据中的线性趋势；(b)以最廉价的方式放置传感器以监测给定区域；以及(c)自动识别肺的医学图像的肺部分。该奖项支持的研究将这些问题的计算机程序视为几何优化算法，在几何优化算法中，我们希望在几个约束条件下最大化某个数量。研究了求解这类优化问题的快速算法的存在性。所研究问题的进展将增强计算几何的核心知识，并扩大图论方法对医学图像分析的影响。这项工作为博士生提供了丰富的训练基地，他们不仅将接触到理论计算几何，而且还将接触到它的一些应用。学生也将在更广泛的方式丰富的研究生课程，近似算法，计算几何，和应用。

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.