1 Search Results for "Corbet, René"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.27
Computing the Multicover Bifiltration

Authors: René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.
Cite as

René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang. Computing the Multicover Bifiltration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{corbet_et_al:LIPIcs.SoCG.2021.27,
  author =	{Corbet, Ren\'{e} and Kerber, Michael and Lesnick, Michael and Osang, Georg},
  title =	{{Computing the Multicover Bifiltration}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.27},
  URN =		{urn:nbn:de:0030-drops-138260},
  doi =		{10.4230/LIPIcs.SoCG.2021.27},
  annote =	{Keywords: Bifiltrations, nerves, higher-order Delaunay complexes, higher-order Voronoi diagrams, rhomboid tiling, multiparameter persistent homology, denoising}
}
  • Refine by Author
  • 1 Corbet, René
  • 1 Kerber, Michael
  • 1 Lesnick, Michael
  • 1 Osang, Georg

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Bifiltrations
  • 1 denoising
  • 1 higher-order Delaunay complexes
  • 1 higher-order Voronoi diagrams
  • 1 multiparameter persistent homology
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact