CAREER: Algorithms for fitting, matching, and simplifying shapes

University Of Iowa, Iowa City IA

Investigators

Abstract

ABSTRACT This 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.