DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2019.11

When Convexity Helps Collapsing Complexes

Authors: Dominique Attali, André Lieutier, and David Salinas

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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.

Cite as

Dominique Attali, André Lieutier, and David Salinas. When Convexity Helps Collapsing Complexes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2019.11,
  author =	{Attali, Dominique and Lieutier, Andr\'{e} and Salinas, David},
  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 =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.11},
  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}
}

Search Results

Documents authored by Salinas, David

When Convexity Helps Collapsing Complexes

Abstract

Cite as

Thanks for your feedback!

Could not send message