Collaborative Research: AF: Small: Shape Matching in a Messy World Using Frechet Distance

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

Shape matching is a computing process that compares data sets based on their interpretation as geometric shapes. Good shape matching methods lead to many useful outcomes including a better understanding of human health, consumer preferences, and patterns in nature. The Frechet distance is often used for shape matching curves describing the movement of people or the shapes of the proteins used as the building blocks of the human body. Its popularity is largely due to its many nice mathematical properties, but there are several issues with its use on real-world data which is often large and messy in nature. Also, the possibilities for expanding its use to settings other than curves are not as well understood. The project seeks to study Frechet distance computing in the presence of messy data. It seeks new methods for computing Frechet distance that can be done quickly even for complicated curves. It also seeks ways to extend the main mathematical ideas behind the Frechet distances to data types other than curves. The project is collaborative and will lead to exchange of knowledge and student training opportunities between the investigators' institutions. It will lead to new shape matching software being made freely available to those who will find it useful. The research activities have three components reflecting the expertise of the project's team of lead researchers. The first component specifically seeks new algorithms for studying messy curve data, focusing on problems designed to address noise and misalignments of the curves' representations. The second component seeks faster and effective approximation algorithms for the Frechet distance and some closely related problems. The third component seeks to apply insights made from work on the first two components to design new algorithms for extensions of the Frechet distance, including a novel interpretation of the so-called discrete Frechet distance in surfaces. Some of the theoretical algorithms designed for this work will be implemented and software made freely available for the general public. The work performed and knowledge gained during the research activities will be used to train new graduate students and offered as course material at the researchers' institutions. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.