CAREER: Algorithms for fitting, matching, and simplifying shapes

摘要本研究的重点是分析、比较和运算形状的有效算法，并解决了三类与形状相关的问题：(1)形状拟合，即将已知的简单形状（如直线）拟合到给定的点集；(2)形状匹配，即估计两个离散形状之间的相似性问题；(3)形状简化，即用更简单的形状代替复杂的形状，同时保留尽可能多的拓扑和几何效率的问题。本研究将这些问题视为几何优化问题，并强调求解这些问题的近似算法的发展。形状拟合是在发现统计数据的趋势或估计制造零件符合其规格的程度时出现的问题。形状匹配是在估计两个物体彼此相似程度时出现的问题；被比较的对象可以是两个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.