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

形状匹配是一种计算过程，它根据数据集的几何形状进行比较。良好的形状匹配方法可以带来许多有用的结果，包括更好地了解人类健康、消费者偏好和自然界的模式。Frechet距离通常用于描述人体运动的形状匹配曲线或用作人体构建块的蛋白质的形状。它的流行很大程度上是由于它的许多很好的数学性质，但是在现实世界的数据中使用它有几个问题，这些数据通常是大而混乱的。此外，将其扩展到曲线以外的设置的可能性还没有得到很好的理解。该项目旨在研究在混乱数据存在下的Frechet距离计算。它寻求计算Frechet距离的新方法，即使对于复杂的曲线也能快速完成。它还寻求将Frechet距离背后的主要数学思想扩展到曲线以外的数据类型的方法。该项目是合作性的，将导致研究机构之间的知识交流和学生培训机会。这将导致新的形状匹配软件被免费提供给那些发现它有用的人。研究活动有三个组成部分，反映了项目首席研究人员团队的专业知识。第一个部分专门寻求研究混乱曲线数据的新算法，重点关注旨在解决曲线表示的噪声和错位的问题。第二部分寻求Frechet距离和一些密切相关问题的更快和有效的逼近算法。第三个部分旨在应用前两个部分的研究成果，设计新的算法来扩展Frechet距离，包括对所谓的曲面离散Frechet距离的新解释。为这项工作设计的一些理论算法将被实现，软件将免费提供给公众。在研究活动中进行的工作和获得的知识将用于培训新的研究生，并作为研究机构的课程材料提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.