8 Search Results for "Buchet, Mickaël"

Document
DOI: 10.4230/LIPIcs.SoCG.2025.6
A Sparse Multicover Bifiltration of Linear Size

Authors: Ángel Javier Alonso

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The k-cover of a point cloud X of ℝ^d at radius r is the set of all those points within distance r of at least k points of X. By varying r and k we obtain a two-parameter filtration known as the multicover bifiltration. This bifiltration has received attention recently due to being choice-free and robust to outliers. However, it is hard to compute: the smallest known equivalent simplicial bifiltration has O(|X|^{d+1}) simplices. In this paper we introduce a (1+ε)-approximation of the multicover bifiltration of linear size O(|X|), for fixed d and ε. The methods also apply to the subdivision Rips bifiltration on metric spaces of bounded doubling dimension yielding analogous results.
Cite as

Ángel Javier Alonso. A Sparse Multicover Bifiltration of Linear Size. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alonso:LIPIcs.SoCG.2025.6,
  author =	{Alonso, \'{A}ngel Javier},
  title =	{{A Sparse Multicover Bifiltration of Linear Size}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.6},
  URN =		{urn:nbn:de:0030-drops-231587},
  doi =		{10.4230/LIPIcs.SoCG.2025.6},
  annote =	{Keywords: Multicover, Approximation, Sparsification, Multiparameter persistence}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.41
Decomposing Multiparameter Persistence Modules

Authors: Tamal K. Dey, Jan Jendrysiak, and Michael Kerber

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Dey and Xin (J.Appl.Comput.Top., 2022) describe an algorithm to decompose finitely presented multiparameter persistence modules using a matrix reduction algorithm. Their algorithm only works for modules whose generators and relations are distinctly graded. We extend their approach to work on all finitely presented modules and introduce several improvements that lead to significant speed-ups in practice. Our algorithm is fixed-parameter tractable with respect to the maximal number of relations of the same degree and with further optimisation we obtain an O(n³) time algorithm for interval-decomposable modules. In particular, we can decide interval-decomposability in this time. As a by-product to the proofs of correctness we develop a theory of parameter restriction for persistence modules. Our algorithm is implemented as a software library aida, the first to enable the decomposition of large inputs. We show its capabilities via extensive experimental evaluation.
Cite as

Tamal K. Dey, Jan Jendrysiak, and Michael Kerber. Decomposing Multiparameter Persistence Modules. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2025.41,
  author =	{Dey, Tamal K. and Jendrysiak, Jan and Kerber, Michael},
  title =	{{Decomposing Multiparameter Persistence Modules}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.41},
  URN =		{urn:nbn:de:0030-drops-231939},
  doi =		{10.4230/LIPIcs.SoCG.2025.41},
  annote =	{Keywords: Topological Data Analysis, Multiparameter Persistence Modules, Persistence, Decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.35
A Theory of Sub-Barcodes

Authors: Oliver A. Chubet, Kirk P. Gardner, and Donald R. Sheehy

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The primary tool in topological data analysis (TDA) is persistent homology, which involves computing a barcode - often from point-cloud or scalar field data - that serves as a topological signature for the underlying function. In this work, we introduce sub-barcodes and show how they arise naturally from factorizations of persistence module homomorphisms. We show that, as a partial order induced by factorizations, the relation of being a sub-barcode is strictly stronger than the rank invariant, and we apply sub-barcode theory to the problem of inferring information about the barcode of an unknown Lipschitz function from samples. The advantage of this approach is that it permits strong guarantees - with no noise - while requiring no sampling assumptions, and the resulting barcode is guaranteed to be a sub-barcode of every Lipschitz function that agrees with the data. We also present an algorithmic theory that allows for the efficient approximation of sub-barcodes using filtered Delaunay triangulations for Euclidean inputs.
Cite as

Oliver A. Chubet, Kirk P. Gardner, and Donald R. Sheehy. A Theory of Sub-Barcodes. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chubet_et_al:LIPIcs.SoCG.2025.35,
  author =	{Chubet, Oliver A. and Gardner, Kirk P. and Sheehy, Donald R.},
  title =	{{A Theory of Sub-Barcodes}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.35},
  URN =		{urn:nbn:de:0030-drops-231873},
  doi =		{10.4230/LIPIcs.SoCG.2025.35},
  annote =	{Keywords: Topology, Topological Data Analysis, Persistent Homology, Persistence Modules, Barcodes, Sub-barcodes, Factorizations, Lipschitz Extensions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.64
Super-Polynomial Growth of the Generalized Persistence Diagram

Authors: Donghan Kim, Woojin Kim, and Wonjun Lee

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The Generalized Persistence Diagram (GPD) for multi-parameter persistence naturally extends the classical notion of persistence diagram for one-parameter persistence. However, unlike its classical counterpart, computing the GPD remains a significant challenge. The main hurdle is that, while the GPD is defined as the Möbius inversion of the Generalized Rank Invariant (GRI), computing the GRI is intractable due to the formidable size of its domain, i.e., the set of all connected and convex subsets in a finite grid in ℝ^d with d ≥ 2. This computational intractability suggests seeking alternative approaches to computing the GPD. In order to study the complexity associated to computing the GPD, it is useful to consider its classical one-parameter counterpart, where for a filtration of a simplicial complex with n simplices, its persistence diagram contains at most n points. This observation leads to the question: Given a d-parameter simplicial filtration, could the cardinality of its GPD (specifically, the support of the GPD) also be bounded by a polynomial in the number of simplices in the filtration? This is the case for d = 1, where we compute the persistence diagram directly at the simplicial filtration level. If this were also the case for d ≥ 2, it might be possible to compute the GPD directly and much more efficiently without relying on the GRI. We show that the answer to the question above is negative, demonstrating the inherent difficulty of computing the GPD. More specifically, we construct a sequence of d-parameter simplicial filtrations where the cardinalities of their GPDs are not bounded by any polynomial in the number of simplices. Furthermore, we show that several commonly used methods for constructing multi-parameter filtrations can give rise to such "wild" filtrations.
Cite as

Donghan Kim, Woojin Kim, and Wonjun Lee. Super-Polynomial Growth of the Generalized Persistence Diagram. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.SoCG.2025.64,
  author =	{Kim, Donghan and Kim, Woojin and Lee, Wonjun},
  title =	{{Super-Polynomial Growth of the Generalized Persistence Diagram}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.64},
  URN =		{urn:nbn:de:0030-drops-232162},
  doi =		{10.4230/LIPIcs.SoCG.2025.64},
  annote =	{Keywords: Persistent homology, M\"{o}bius inversion, Multiparameter persistence, Generalized persistence diagram, Generalized rank invariant}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.20
Sparse Higher Order Čech Filtrations

Authors: Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
For a finite set of balls of radius r, the k-fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k-fold filtration of the centers. For k = 1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k = 1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points.
Cite as

Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber. Sparse Higher Order Čech Filtrations. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2023.20,
  author =	{Buchet, Micka\"{e}l and B. Dornelas, Bianca and Kerber, Michael},
  title =	{{Sparse Higher Order \v{C}ech Filtrations}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.20},
  URN =		{urn:nbn:de:0030-drops-178709},
  doi =		{10.4230/LIPIcs.SoCG.2023.20},
  annote =	{Keywords: Sparsification, k-fold cover, Higher order \v{C}ech complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.15
Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension

Authors: Mickaël Buchet and Emerson G. Escolar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
While persistent homology has taken strides towards becoming a widespread tool for data analysis, multidimensional persistence has proven more difficult to apply. One reason is the serious drawback of no longer having a concise and complete descriptor analogous to the persistence diagrams of the former. We propose a simple algebraic construction to illustrate the existence of infinite families of indecomposable persistence modules over regular grids of sufficient size. On top of providing a constructive proof of representation infinite type, we also provide realizations by topological spaces and Vietoris-Rips filtrations, showing that they can actually appear in real data and are not the product of degeneracies.
Cite as

Mickaël Buchet and Emerson G. Escolar. Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2018.15,
  author =	{Buchet, Micka\"{e}l and Escolar, Emerson G.},
  title =	{{Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.15},
  URN =		{urn:nbn:de:0030-drops-87287},
  doi =		{10.4230/LIPIcs.SoCG.2018.15},
  annote =	{Keywords: persistent homology, multi-persistence, representation theory, quivers, commutative ladders, Vietoris-Rips filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.23
Declutter and Resample: Towards Parameter Free Denoising

Authors: Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of K. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases. Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms are effective in practice.
Cite as

Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Declutter and Resample: Towards Parameter Free Denoising. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2017.23,
  author =	{Buchet, Mickael and Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Declutter and Resample: Towards Parameter Free Denoising}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.23},
  URN =		{urn:nbn:de:0030-drops-72133},
  doi =		{10.4230/LIPIcs.SoCG.2017.23},
  annote =	{Keywords: denoising, parameter free, k-distance,compact sets}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.827
Topological Analysis of Scalar Fields with Outliers

Authors: Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Given a real-valued function f defined over a manifold M embedded in R^d, we are interested in recovering structural information about f from the sole information of its values on a finite sample P. Existing methods provide approximation to the persistence diagram of f when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.
Cite as

Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang. Topological Analysis of Scalar Fields with Outliers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 827-841, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SOCG.2015.827,
  author =	{Buchet, Micka\"{e}l and Chazal, Fr\'{e}d\'{e}ric and Dey, Tamal K. and Fan, Fengtao and Oudot, Steve Y. and Wang, Yusu},
  title =	{{Topological Analysis of Scalar Fields with Outliers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{827--841},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.827},
  URN =		{urn:nbn:de:0030-drops-51052},
  doi =		{10.4230/LIPIcs.SOCG.2015.827},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Scalar Field Analysis, Nested Rips Filtration, Distance to a Measure}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2023
  • 1 2018
  • 1 2017
  • 1 2015

  • Refine by Author
  • 3 Buchet, Mickaël
  • 3 Dey, Tamal K.
  • 2 Kerber, Michael
  • 2 Wang, Yusu
  • 1 Alonso, Ángel Javier
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Algebraic topology
  • 3 Theory of computation → Computational geometry
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Topology
  • Show More...

  • Refine by Keyword
  • 3 Topological Data Analysis
  • 2 Multiparameter persistence
  • 2 Persistent Homology
  • 2 Sparsification
  • 1 Approximation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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