CAREER: Mapping Problems in Computational Geometry and Topology

职业：计算几何和拓扑中的绘图问题

基本信息

批准号：
1941086
负责人：
Amir Nayyeri
金额：
$ 60万
依托单位：
Oregon State University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2025-09-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1941086&HistoricalAwards=false
关键词：
CAREER Mapping Problems Computational Geometry

项目摘要

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.

测量对象之间的相似性是许多应用中普遍存在的基本问题，包括医学图像处理中的配准、蛋白质建模中的功能检测、系统基因组学中的重建进化树以及数据分析中的重复模式的研究。该项目从可计算性和有效性的角度研究了不同的相似性度量，并将所有相似性度量视为对象之间的映射。不同的几何形状和具体来说，该奖项的研究重点在于以下二分法：一方面，通常很难计算甚至近似数学上精确的相似性度量，这些相似性度量被抽象地研究为计算几何中的几何形状匹配和度量嵌入问题。另一方面，针对缺乏理论保证的特定应用程序设计了更快的启发式方法，因此不可推广。二分法是机会——该项目将使用参数化的复杂性来更好地理解复杂性。使用不同的表示和属性计算度量空间之间的相似性度量如果成功，该奖项的研究将产生具有新性能保证的新算法，特别是对于实际感兴趣的情况，测量几何对象之间的相似性是许多人面临的基本问题。应用程序，因此该项目及其培训的学生将对许多领域的理论和实践产生重大影响。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology

坍缩宇宙中的计算拓扑：拉普拉斯算子、同调、上同调

DOI：
发表时间：
2022-01
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Mitchell Black; William Maxwell
通讯作者：
William Maxwell

Minimum Cuts in Surface Graphs

曲面图中的最小割