CRII: AF: Measuring similarity between geometric objects

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

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.