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.11
URN: urn:nbn:de:0030-drops-104152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10415/
Go to the corresponding LIPIcs Volume Portal

Attali, Dominique ; Lieutier, André ; Salinas, David

When Convexity Helps Collapsing Complexes

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

Abstract

This paper illustrates how convexity hypotheses help collapsing simplicial complexes. We first consider a collection of compact convex sets and show that the nerve of the collection is collapsible whenever the union of sets in the collection is convex. We apply this result to prove that the Delaunay complex of a finite point set is collapsible. We then consider a convex domain defined as the convex hull of a finite point set. We show that if the point set samples sufficiently densely the domain, then both the Cech complex and the Rips complex of the point set are collapsible for a well-chosen scale parameter. A key ingredient in our proofs consists in building a filtration by sweeping space with a growing sphere whose center has been fixed and studying events occurring through the filtration. Since the filtration mimics the sublevel sets of a Morse function with a single critical point, we anticipate this work to lay the foundations for a non-smooth, discrete Morse Theory.

BibTeX - Entry

@InProceedings{attali_et_al:LIPIcs:2019:10415,
  author =	{Dominique Attali and Andr{\'e} Lieutier and David Salinas},
  title =	{{When Convexity Helps Collapsing Complexes}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{11:1--11: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/10415},
  URN =		{urn:nbn:de:0030-drops-104152},
  doi =		{10.4230/LIPIcs.SoCG.2019.11},
  annote =	{Keywords: collapsibility, convexity, collection of compact convex sets, nerve, filtration, Delaunay complex, Cech complex, Rips complex}
}

Keywords: collapsibility, convexity, collection of compact convex sets, nerve, filtration, Delaunay complex, Cech complex, Rips complex
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