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

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

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.