Computing the Multicover Bifiltration.
Saved in:
| Title: | Computing the Multicover Bifiltration. |
|---|---|
| Authors: | Corbet, René1 (AUTHOR) corbet@kth.se, Kerber, Michael2 (AUTHOR), Lesnick, Michael3 (AUTHOR), Osang, Georg4 (AUTHOR) |
| Source: | Discrete & Computational Geometry. Sep2023, Vol. 70 Issue 2, p376-405. 30p. |
| Subjects: | Point set theory, Polyhedral functions |
| Abstract: | Given a finite set A ⊂ R 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. 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 169913223 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Computing the Multicover Bifiltration. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Corbet%2C+René%22">Corbet, René</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> corbet@kth.se</i><br /><searchLink fieldCode="AR" term="%22Kerber%2C+Michael%22">Kerber, Michael</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Lesnick%2C+Michael%22">Lesnick, Michael</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Osang%2C+Georg%22">Osang, Georg</searchLink><relatesTo>4</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Sep2023, Vol. 70 Issue 2, p376-405. 30p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Point+set+theory%22">Point set theory</searchLink><br /><searchLink fieldCode="DE" term="%22Polyhedral+functions%22">Polyhedral functions</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Given a finite set A ⊂ R 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. 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=169913223 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-022-00476-8 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 30 StartPage: 376 Subjects: – SubjectFull: Point set theory Type: general – SubjectFull: Polyhedral functions Type: general Titles: – TitleFull: Computing the Multicover Bifiltration. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Corbet, René – PersonEntity: Name: NameFull: Kerber, Michael – PersonEntity: Name: NameFull: Lesnick, Michael – PersonEntity: Name: NameFull: Osang, Georg IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2023 Type: published Y: 2023 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 70 – Type: issue Value: 2 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
