Finding small holes a brief foray into computational topology

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
Number of pages1
ISBN (Print)3540739483, 9783540739487
StatePublished - 2007
Event10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada
Duration: Aug 15 2007Aug 17 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4619 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th International Workshop on Algorithms and Data Structures, WADS 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Finding small holes a brief foray into computational topology'. Together they form a unique fingerprint.

Cite this