License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.55
URN: urn:nbn:de:0030-drops-104596
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10459/
Go to the corresponding LIPIcs Volume Portal

Boissonnat, Jean-Daniel ; Pritam, Siddharth

Computing Persistent Homology of Flag Complexes via Strong Collapses

pdf-format:
LIPIcs-SoCG-2019-55.pdf (0.5 MB)

Abstract

In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.

BibTeX - Entry

@InProceedings{boissonnat_et_al:LIPIcs:2019:10459,
  author =	{Jean-Daniel Boissonnat and Siddharth Pritam},
  title =	{{Computing Persistent Homology of Flag Complexes via Strong Collapses}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10459},
  URN =		{urn:nbn:de:0030-drops-104596},
  doi =		{10.4230/LIPIcs.SoCG.2019.55},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}

Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI