Finding small holes a brief foray into computational topology

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

Abstract

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
PublisherSpringer-Verlag Berlin Heidelberg
Number of pages1
ISBN (Print)3540739483, 9783540739487
DOIs
StatePublished - Jan 1 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

Other

Other10th International Workshop on Algorithms and Data Structures, WADS 2007
CountryCanada
CityHalifax
Period8/15/078/17/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this