kth.sePublikationer KTH
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Computing the multicover bifiltration
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).ORCID-id: 0000-0003-3148-4039
2021 (Engelska)Ingår i: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2021Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Given a finite set A ⊂ ℝd, let Covr,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. 

Ort, förlag, år, upplaga, sidor
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2021.
Nyckelord [en]
Bifiltrations, Denoising, Higher-order Delaunay complexes, Higher-order Voronoi diagrams, Multiparameter persistent homology, Nerves, Rhomboid tiling, Topology, Finite set, K points, Computational geometry
Nationell ämneskategori
Datavetenskap (datalogi) Algebra och logik Beräkningsmatematik
Identifikatorer
URN: urn:nbn:se:kth:diva-309944DOI: 10.4230/LIPIcs.SoCG.2021.27Scopus ID: 2-s2.0-85108226630OAI: oai:DiVA.org:kth-309944DiVA, id: diva2:1645889
Konferens
37th International Symposium on Computational Geometry, SoCG 2021, 7 June 2021 through 11 June 2021
Anmärkning

Part of proceedings: ISBN 978-3-95977-184-9

QC 20220321

Tillgänglig från: 2022-03-21 Skapad: 2022-03-21 Senast uppdaterad: 2023-01-18Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Corbet, René

Sök vidare i DiVA

Av författaren/redaktören
Corbet, René
Av organisationen
Matematik (Inst.)
Datavetenskap (datalogi)Algebra och logikBeräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 136 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf