CAREER: Algorithms for fitting, matching, and simplifying shapes

本文研究了形状的分析、比较和操作的有效算法，主要涉及三类与形状有关的问题：（1）形状拟合，即把已知的简单形状（如直线）拟合到给定的点集上的问题;（2）形状匹配，即估计两个离散形状之间的相似性的问题;（3）形状简化，这是用较简单的形状替换复杂的形状，同时保持尽可能多的拓扑和几何有效性的问题。本研究认为这些问题的几何优化问题，并强调发展的近似算法来解决them.Shape拟合是一个问题，出现在发现趋势的统计数据或估计如何以及制造的零件符合其规格。形状匹配是在估计两个对象彼此相似程度时出现的问题;被比较的对象可以是生物识别应用中的两个Web文档或两个人类图像。在飞行模拟等场景中，当试图以适当的细节级别显示场景时，形状简化是一个重要的问题。本研究将这些问题的计算机程序视为几何优化算法，我们希望在几个约束条件下最大化某个数量。试图找到此类问题的最佳解决方案的算法通常太慢而无法实际使用。这项研究强调近似算法，该算法在最佳解的已知公差范围内找到解，而不是最佳解。在大多数应用中，近似最佳值就足够了。近似算法通常比找到最佳解的算法更快、更简单、更鲁棒。这项研究的主要目标是发现强大的技术开发这样的近似算法。

ABSTRACTThis research is focused on efficient algorithms for analyzing, comparing, and operating on shapes, and addresses three classes of problems connected with shapes: (1) Shape fitting, which is the problem of fitting a known simple shape, such as a line, to a given set of points; (2) Shape matching, which is the problem of estimating the similarity between two discretized shapes; and (3) Shape simplification, which is the problem of replacing a complex shape with a simpler one while preserving as much of the topology and geometry efficient as specified. This research views these problems as geometric optimization problems and emphasizes the development of approximation algorithms for solving them.Shape fitting is a problem that arises in discovering trends in statistical data or in estimating how well a manufactured part meets its specifications. Shape matching is a problem that arises in estimating how closely two objects resemble each other; the objects being compared could be two web documents or two human images in a biometrics application. Shape simplification is an important problem in scenarios such as flight simulation when trying to display a scene at the appropriate level of detail. This research views computer programs for these problems as algorithms for geometric optimization, where we want to maximize a certain quantity subject to several constraints. Algorithms that try to find the best solution to such problems are often too slow to be of practical use. This research emphasizes approximation algorithms, which find a solution within a known tolerance of the best solution rather than the best solution. In most applications an approximate optimum is sufficient. Approximation algorithms are generally considerably faster, simpler, and more robust than algorithms that find the best solution. The main goal of this research is to discover powerful techniques for developing such approximation algorithms.