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

形状匹配是一个计算过程，它根据数据集作为几何形状的解释来比较数据集。良好的形状匹配方法可以产生许多有用的结果，包括更好地了解人类健康，消费者偏好和自然界的模式。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.