5 Search Results for "Glisse, Marc"


Document
Swap, Shift and Trim to Edge Collapse a Filtration

Authors: Marc Glisse and Siddharth Pritam

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit the use of edge collapse for efficient computation of persistent homology. We first give a simple and intuitive explanation of the principles underlying that algorithm. This in turn allows us to propose various extensions including a zigzag filtration simplification algorithm. We finally show some experiments to better understand how it behaves.

Cite as

Marc Glisse and Siddharth Pritam. Swap, Shift and Trim to Edge Collapse a Filtration. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{glisse_et_al:LIPIcs.SoCG.2022.44,
  author =	{Glisse, Marc and Pritam, Siddharth},
  title =	{{Swap, Shift and Trim to Edge Collapse a Filtration}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.44},
  URN =		{urn:nbn:de:0030-drops-160525},
  doi =		{10.4230/LIPIcs.SoCG.2022.44},
  annote =	{Keywords: edge collapse, flag complex, graph, persistent homology}
}
Document
Edge Collapse and Persistence of Flag Complexes

Authors: Jean-Daniel Boissonnat and Siddharth Pritam

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appears to be a very powerful concept, especially when applied to flag complexes. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude w.r.t the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.

Cite as

Jean-Daniel Boissonnat and Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.19,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth},
  title =	{{Edge Collapse and Persistence of Flag Complexes}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.19},
  URN =		{urn:nbn:de:0030-drops-121777},
  doi =		{10.4230/LIPIcs.SoCG.2020.19},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology}
}
Document
Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets

Authors: Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worst-case quadratic complexity. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)-samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Cite as

Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse. Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2019.22,
  author =	{Boissonnat, Jean-Daniel and Devillers, Olivier and Dutta, Kunal and Glisse, Marc},
  title =	{{Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.22},
  URN =		{urn:nbn:de:0030-drops-111437},
  doi =		{10.4230/LIPIcs.ESA.2019.22},
  annote =	{Keywords: Randomized incremental construction, Delaunay triangulations, Voronoi diagrams, polyhedral surfaces, probabilistic analysis}
}
Document
DTM-Based Filtrations

Authors: Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda

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


Abstract
Despite strong stability properties, the persistent homology of filtrations classically used in Topological Data Analysis, such as, e.g. the Čech or Vietoris-Rips filtrations, are very sensitive to the presence of outliers in the data from which they are computed. In this paper, we introduce and study a new family of filtrations, the DTM-filtrations, built on top of point clouds in the Euclidean space which are more robust to noise and outliers. The approach adopted in this work relies on the notion of distance-to-measure functions and extends some previous work on the approximation of such functions.

Cite as

Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. DTM-Based Filtrations. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{anai_et_al:LIPIcs.SoCG.2019.58,
  author =	{Anai, Hirokazu and Chazal, Fr\'{e}d\'{e}ric and Glisse, Marc and Ike, Yuichi and Inakoshi, Hiroya and Tinarrage, Rapha\"{e}l and Umeda, Yuhei},
  title =	{{DTM-Based Filtrations}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-104623},
  doi =		{10.4230/LIPIcs.SoCG.2019.58},
  annote =	{Keywords: Topological Data Analysis, Persistent homology}
}
Document
On the Smoothed Complexity of Convex Hulls

Authors: Olivier Devillers, Marc Glisse, Xavier Goaoc, and Rémy Thomasse

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


Abstract
We establish an upper bound on the smoothed complexity of convex hulls in R^d under uniform Euclidean (L^2) noise. Specifically, let {p_1^*, p_2^*, ..., p_n^*} be an arbitrary set of n points in the unit ball in R^d and let p_i = p_i^* + x_i, where x_1, x_2, ..., x_n are chosen independently from the unit ball of radius r. We show that the expected complexity, measured as the number of faces of all dimensions, of the convex hull of {p_1, p_2, ..., p_n} is O(n^{2-4/(d+1)} (1+1/r)^{d-1}); the magnitude r of the noise may vary with n. For d=2 this bound improves to O(n^{2/3} (1+r^{-2/3})). We also analyze the expected complexity of the convex hull of L^2 and Gaussian perturbations of a nice sample of a sphere, giving a lower-bound for the smoothed complexity. We identify the different regimes in terms of the scale, as a function of n, and show that as the magnitude of the noise increases, that complexity varies monotonically for Gaussian noise but non-monotonically for L^2 noise.

Cite as

Olivier Devillers, Marc Glisse, Xavier Goaoc, and Rémy Thomasse. On the Smoothed Complexity of Convex Hulls. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 224-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SOCG.2015.224,
  author =	{Devillers, Olivier and Glisse, Marc and Goaoc, Xavier and Thomasse, R\'{e}my},
  title =	{{On the Smoothed Complexity of Convex Hulls}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{224--239},
  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.224},
  URN =		{urn:nbn:de:0030-drops-51451},
  doi =		{10.4230/LIPIcs.SOCG.2015.224},
  annote =	{Keywords: Probabilistic analysis, Worst-case analysis, Gaussian noise}
}
  • Refine by Author
  • 4 Glisse, Marc
  • 2 Boissonnat, Jean-Daniel
  • 2 Devillers, Olivier
  • 2 Pritam, Siddharth
  • 1 Anai, Hirokazu
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Algebraic topology
  • 1 Mathematics of computing → Topology

  • Refine by Keyword
  • 2 Persistent homology
  • 2 Topological Data Analysis
  • 1 Computational Topology
  • 1 Delaunay triangulations
  • 1 Edge Collapse
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2015
  • 1 2020
  • 1 2022

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