CRII: AF: Measuring similarity between geometric objects

Oregon State University, Corvallis OR

Investigators

Abstract

Measuring similarity between geometric objects is a common task in many applications: detecting change in a medical scan, recognizing and indexing content in an image or video, comparing protein structures, or automatically picking the right object from a conveyor belt. Input images, shapes, or models come in different representations that have to be transformed to compare them to a large database of possibilities. This project explores transformations of certain classes (nearly affine transformations) using tools like limited Frechet distance and small metric distortions. Specific proposed problems include computing Frechet distances between terrains and between polygons with holes. Both fixed parameter tractable exact algorithms and polygonal time approximation algorithms will be studied for these problems. The project will also consider the hardness of approximation. For the topic of metric distortions, the proposed problems include computing metric distortions between simple polygons and between discrete point sets. Both exact and approximation algorithms will be studied. The goal is not only to understand the mathematics behind exact transformations, but also to see if approximate transformations will allow faster algorithms with some quality guarantees; most application of similarity measure at present is heuristic, and does not come with guarantees. Measuring similarity between geometric objects is a fundamental problem and has many applications, so this project, and the students that it trains, will have potential impact on theory and practice in many areas.