Finding Small Holes

摘要

Numerous applications call for the detection of small topological features in various spaces; examples include simplification of surfaces reconstructed from point clouds, efficient algorithms for graphs embedded on surfaces, coverage analysis for ad-hoc/sensor networks, and topological analysis of high-dimensional data. This talk is a survey algorithms for one of the simplest problems of this type: finding the shortest cycle in a given topological space that cannot be continuously contracted to a point. Spaces of interest include polygons with holes, combinatorial surfaces, piecewise-linear 2-manifolds, Rips-Vietoris complexes, and general simplicial complexes. Almost no optimal algorithms are known, even in settings where the problem has a straightforward polynomial-time solution; consequently, the talk will include several open problems. No prior knowledge of topology will be assumed.