CRII: AF: Measuring similarity between geometric objects

测量几何对象之间的相似性是许多应用中的常见任务：检测医学扫描中的变化，识别和索引图像或视频中的内容，比较蛋白质结构，或从传送带上自动拾取正确的对象。输入图像、形状或模型以不同的表示形式出现，必须进行转换以将它们与大型可能性数据库进行比较。这个项目探索了某些类的转换（近仿射转换），使用有限的弗雷歇距离和小度量失真等工具。具体提出的问题包括计算地形之间的弗雷歇距离和多边形之间的洞。固定参数易处理的精确算法和多边形时间近似算法将研究这些问题。该项目还将考虑近似的难度。对于度量失真的主题，所提出的问题包括计算简单多边形之间和离散点集之间的度量失真。精确算法和近似算法都将被研究。我们的目标不仅是理解精确变换背后的数学，而且还要看看近似变换是否会允许更快的算法，并具有一定的质量保证;目前大多数相似性度量的应用都是启发式的，并且没有保证。几何对象之间的相似性度量是一个基本问题，有很多应用，所以这个项目，它培养的学生，将在许多领域的理论和实践产生潜在的影响。

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.