Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:Oregon State University
  • Amir Nayyeri
  • (541) 737-4933
Award Date:01/16/2020
Estimated Total Award Amount: $ 600,000
Funds Obligated to Date: $ 107,074
  • FY 2020=$107,074
Start Date:10/01/2020
End Date:09/30/2025
Transaction Type:Grant
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.070
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:CAREER: Mapping Problems in Computational Geometry and Topology
Federal Award ID Number:1941086
DUNS ID:053599908
Parent DUNS ID:053599908
Program:Algorithmic Foundations
Program Officer:
  • Joseph Maurice Rojas
  • (703) 292-8455

Awardee Location

Awardee Cong. District:04

Primary Place of Performance

Organization Name:Oregon State University
Cong. District:04

Abstract at Time of Award

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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.