CAREER: Mapping Problems in Computational Geometry and Topology

相似性度量是医学图像处理中的配准、蛋白质建模中的功能检测、生物基因组学中的进化树重建以及数据分析中的重复模式发现等应用中普遍存在的一个基本问题。 在工程和计算机科学的一系列问题中，已经研究了不同的相似性度量，从非常准确但难以计算到不太准确但可有效计算。 本项目从可计算性和有效性的角度研究不同的相似性度量。 它将所有相似性度量视为对象之间的映射，并考虑对象的不同几何和拓扑表示。具体而言，该奖项的研究重点是以下二分法。 一方面，在计算几何和拓扑学中，相似性度量通常很难计算，甚至难以近似，抽象地研究了几何形状匹配和度量嵌入问题。 另一方面，有更快的算法设计用于缺乏理论保证的特定应用，因此是不可推广的。在二分法是机会-这个项目将使用参数化的复杂性，以创建一个更好的理解使用不同的表示和属性的度量空间之间的计算相似性措施的复杂性。 如果成功，该奖项的研究将产生具有新性能保证的新算法，特别是对于实际感兴趣的情况。几何物体之间的相似性测量是一个具有许多应用的基本问题，因此该项目及其培养的学生将在许多领域的理论和实践中产生重大影响。该奖项反映了NSF的法定使命，通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Measuring similarity between objects is a fundamental problem prevalent in many applications, including registration in medical image processing, function detection in protein modeling, reconstructing evolutionary trees in phylogenomics, and finding recurrent patterns in data analysis. Different measures of similarity have been studied for a range of problems in engineering and computer science, ranging from very accurate but hard to compute to less accurate but efficiently computable. This project studies different similarity measures from the computability and effectiveness point of view. It views all similarity measures as maps between objects, and considers different geometric and topological representations of the objects. Specifically, the research of this award focuses on the following dichotomy. On one hand, it is often hard to compute or even approximate mathematically accurate similarity measures, studied abstractly as geometric shape matching and metric embedding problems in computational geometry and topology. On the other hand, there are faster heuristics engineered for specific applications that lack theoretical guarantees, hence are not generalizable. In dichotomy is opportunity – this project will use parameterized complexity to create a finer understanding of the complexity of computing similarity measures between metric spaces using different representations and properties. If successful, the research of this award will result in new algorithms with new performance guarantees, in particular, for cases of practical interest. Measuring similarity between geometric objects is a fundamental problem with numerous applications, so this project, and the students that it trains, will have significant impact on theory and practice in many areas.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.