AF: Small: Extending algorithms for topological notions of similarity

Saint Louis University, Saint Louis MO

Investigators

Abstract

How would you measure the closeness of two signatures or two clay figurines? This project explores the mathematics and computation of measuring similarity between curves or 3-dimensional objects -- whether to compare GPS tracking data to road maps, or medical scans of internal organs to reference models of healthy organs. While some well understood comparison methods simply look at how close the objects are, this project aims to design more sophisticated measures that take into account the underlying structure (or topology) of the curves and surfaces. The PI plans to collaborate with applications areas that use these measurement algorithms to develop measures that best fit the areas, in addition to continuing her work in a larger network of shape analysis and computational topology communities, including organizing workshops focused at mentoring junior women in these areas. This project generalizes notions of similarity from curves to graphs, meshes, or 3-manifolds. The primary problems and techniques come from the emerging field of computational topology, which combines algorithms and computational geometry with mathematical foundations and tools from the area of topology. In particular, the PI proposes to examine fundamental topological notions of similarity between curves and surfaces in some ambient space, based on computing optimal homotopies, homologies, or isotopies. Each possibility offers a different notion of what it means for two things to be equivalent in the ambient space, and each can be optimized based on the notions of area, "height," or "width." While several initial algorithmic results on these measures have been published, there are many open questions that remain. In addition, recent mathematical developments indicate many potentially tractable and feasible areas that are yet to be explored from the algorithmic perspective. Some of these measures are likely to be hard to compute, which is of interest to the theoretical community, and approximation or fixed parameter tractable algorithms may prove practical in applications areas. The project will also include collaborations in applications areas for these measures, in order to better evaluate their utility.