Search Results

Documents authored by Boissonnat, Jean-Daniel

Document
DOI: 10.4230/LIPIcs.ESA.2024.29
A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels

Authors: Jean-Daniel Boissonnat and Kunal Dutta

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, unlike in the case of persistent homology computation using the Euclidean distance or the k-distance, using Gaussian kernels involves significantly higher overhead, as all distance computations are in terms of the Gaussian kernel distance which is computationally more expensive. Further, most algorithmic implementations (e.g. Gudhi, Ripser, etc.) are based on Euclidean distances, so the question of finding a Euclidean embedding - preferably low-dimensional - that preserves the persistent homology computed with Gaussian kernels, is quite important. We consider the Gaussian kernel power distance (GKPD) given by Phillips, Wang and Zheng. Given an n-point dataset and a relative error parameter {ε} ∈ (0,1], we show that the persistent homology of the {Čech } filtration of the dataset computed using the GKPD can be approximately preserved using O({ε}^{-2}log n) dimensions, under a high stable rank condition. Our results also extend to the Delaunay filtration and the (simpler) case of the weighted Rips filtrations constructed using the GKPD. Compared to the Euclidean embedding for the Gaussian kernel function in ∼ n dimensions, which uses the Cholesky decomposition of the matrix of the kernel function applied to all pairs of data points, our embedding may also be viewed as dimensionality reduction - reducing the dimensionality from n to ∼ log n dimensions. Our proof utilizes the embedding of Chen and Phillips [ALT 2017], based on the Random Fourier Functions of Rahimi and Recht [NeurIPS 2007], together with two novel ingredients. The first one is a new decomposition of the squared radii of {Čech } simplices computed using the GKPD, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second is a new concentration inequality for sums of cosine functions of Gaussian random vectors, which we call Gaussian cosine chaoses. We believe these are of independent interest and will find other applications in future.
Cite as

Jean-Daniel Boissonnat and Kunal Dutta. A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2024.29,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal},
  title =	{{A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.29},
  URN =		{urn:nbn:de:0030-drops-211009},
  doi =		{10.4230/LIPIcs.ESA.2024.29},
  annote =	{Keywords: Persistent homology, Gaussian kernels, Random Fourier Features, Euclidean embedding}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.21
On Edge Collapse of Random Simplicial Complexes

Authors: Jean-Daniel Boissonnat, Kunal Dutta, Soumik Dutta, and Siddharth Pritam

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We consider the edge collapse (introduced in [Boissonnat, Pritam. SoCG 2020]) process on the Erdős-Rényi random clique complex X(n,c/√n) on n vertices with edge probability c/√n such that c > √η₂ where η₂ = inf{η | x = e^{-η(1-x)²} has a solution in (0,1)}. For a given c > √η₂, we show that after t iterations of maximal edge collapsing phases, the remaining subcomplex, or t-core, has at most (1+o(1))binom(n,2)p(1-(c²/3)(1-(1-γ_t)³)) and at least (1+o(1)) binom(n,2) p(1-γ_{t+1}-c²γ_t(1-γ_t)²) edges asymptotically almost surely (a.a.s.), where {γ_t}_{t ≥ 0} is recursively determined by γ_{t+1} = e^{-c²(1-γ_t)²} and γ_0 = 0. We also determine the upper and lower bound on the final core with explicit formulas. If c < √{η₂} then we show that the final core contains o(n√n) edges. On the other hand, if, instead of c being a constant with respect to n, c > √{2log n} then the edge collapse process is no more effective in reducing the size of the complex. Our proof is based on the notion of local weak convergence [Aldous, Steele. In Probability on discrete structures. Springer, 2004] together with two new components. Firstly, we identify the critical combinatorial structures that control the outcome of the edge collapse process. By controlling the expected number of these structures during the edge collapse process we establish a.a.s. bounds on the size of the core. We also give a new concentration inequality for typically Lipschitz functions on random graphs which improves on the bound of [Warnke. Combinatorics, Probability and Computing, 2016] and is, therefore, of independent interest. The proof of our lower bound is via the recursive technique of [Linial and Peled. A Journey Through Discrete Mathematics. 2017] to simulate cycles in infinite trees. These are the first theoretical results proved for edge collapses on random (or non-random) simplicial complexes.
Cite as

Jean-Daniel Boissonnat, Kunal Dutta, Soumik Dutta, and Siddharth Pritam. On Edge Collapse of Random Simplicial Complexes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2024.21,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal and Dutta, Soumik and Pritam, Siddharth},
  title =	{{On Edge Collapse of Random Simplicial Complexes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.21},
  URN =		{urn:nbn:de:0030-drops-199661},
  doi =		{10.4230/LIPIcs.SoCG.2024.21},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Simple Collapse, Persistent homology, Random simplicial complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.17
Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations

Authors: Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken

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

Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.
Cite as

Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken. Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2021.17,
  author =	{Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
  title =	{{Tracing Isomanifolds in \mathbb{R}^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{17:1--17:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.17},
  URN =		{urn:nbn:de:0030-drops-138163},
  doi =		{10.4230/LIPIcs.SoCG.2021.17},
  annote =	{Keywords: Coxeter triangulation, Kuhn triangulation, permutahedron, PL-approximations, isomanifolds/solution manifolds/isosurfacing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.10
Dimensionality Reduction for k-Distance Applied to Persistent Homology

Authors: Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, and Martin Lotz

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

Abstract
Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor. We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively.
Cite as

Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, and Martin Lotz. Dimensionality Reduction for k-Distance Applied to Persistent Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SoCG.2020.10,
  author =	{Arya, Shreya and Boissonnat, Jean-Daniel and Dutta, Kunal and Lotz, Martin},
  title =	{{Dimensionality Reduction for k-Distance Applied to Persistent Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-121682},
  doi =		{10.4230/LIPIcs.SoCG.2020.10},
  annote =	{Keywords: Dimensionality reduction, Johnson-Lindenstrauss lemma, Topological Data Analysis, Persistent Homology, k-distance, distance to measure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.19
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
DOI: 10.4230/LIPIcs.SoCG.2020.20
The Topological Correctness of PL-Approximations of Isomanifolds

Authors: Jean-Daniel Boissonnat and Mathijs Wintraecken

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

Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.
Cite as

Jean-Daniel Boissonnat and Mathijs Wintraecken. The Topological Correctness of PL-Approximations of Isomanifolds. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.20,
  author =	{Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
  title =	{{The Topological Correctness of PL-Approximations of Isomanifolds}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{20:1--20:18},
  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.20},
  URN =		{urn:nbn:de:0030-drops-121787},
  doi =		{10.4230/LIPIcs.SoCG.2020.20},
  annote =	{Keywords: PL-approximations, isomanifolds, solution manifolds, topological correctness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.22
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
DOI: 10.4230/LIPIcs.SoCG.2019.55
Computing Persistent Homology of Flag Complexes via Strong Collapses

Authors: Jean-Daniel Boissonnat and Siddharth Pritam

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

Abstract
In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.
Cite as

Jean-Daniel Boissonnat and Siddharth Pritam. Computing Persistent Homology of Flag Complexes via Strong Collapses. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2019.55,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth},
  title =	{{Computing Persistent Homology of Flag Complexes via Strong Collapses}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{55:1--55: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.55},
  URN =		{urn:nbn:de:0030-drops-104596},
  doi =		{10.4230/LIPIcs.SoCG.2019.55},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.67
Strong Collapse for Persistence

Authors: Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We introduce a fast and memory efficient approach to compute the persistent homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexes of the input sequence by using strong collapses, as introduced by J. Barmak and E. Miniam [DCG (2012)], and to compute the PH of an induced sequence of reduced simplicial complexes that has the same PH as the initial one. Our approach has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of all its simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel. As a result and as demonstrated by numerous experiments on publicly available data sets, our approach is extremely fast and memory efficient in practice.
Cite as

Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek. Strong Collapse for Persistence. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 67:1-67:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2018.67,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth and Pareek, Divyansh},
  title =	{{Strong Collapse for Persistence}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{67:1--67:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.67},
  URN =		{urn:nbn:de:0030-drops-95302},
  doi =		{10.4230/LIPIcs.ESA.2018.67},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.9
Local Criteria for Triangulation of Manifolds

Authors: Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken

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

Abstract
We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.
Cite as

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. Local Criteria for Triangulation of Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2018.9,
  author =	{Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Wintraecken, Mathijs},
  title =	{{Local Criteria for Triangulation of Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{9:1--9:14},
  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.9},
  URN =		{urn:nbn:de:0030-drops-87224},
  doi =		{10.4230/LIPIcs.SoCG.2018.9},
  annote =	{Keywords: manifold, simplicial complex, homeomorphism, triangulation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.10
The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces

Authors: Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken

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

Abstract
In this paper we discuss three results. The first two concern general sets of positive reach: We first characterize the reach by means of a bound on the metric distortion between the distance in the ambient Euclidean space and the set of positive reach. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the distance between the points and the reach.
Cite as

Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2018.10,
  author =	{Boissonnat, Jean-Daniel and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{10:1--10:14},
  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.10},
  URN =		{urn:nbn:de:0030-drops-87236},
  doi =		{10.4230/LIPIcs.SoCG.2018.10},
  annote =	{Keywords: Reach, Metric distortion, Manifolds, Convexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.25
Kernelization of the Subset General Position Problem in Geometry

Authors: Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, and Sudeshna Kolay

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations. When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k, or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic assumptions. We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.
Cite as

Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, and Sudeshna Kolay. Kernelization of the Subset General Position Problem in Geometry. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.MFCS.2017.25,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal and Ghosh, Arijit and Kolay, Sudeshna},
  title =	{{Kernelization of the Subset General Position Problem in Geometry}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.25},
  URN =		{urn:nbn:de:0030-drops-80863},
  doi =		{10.4230/LIPIcs.MFCS.2017.25},
  annote =	{Keywords: Incidence Geometry, Kernel Lower bounds, Hyperplanes, Bounded degree polynomials}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.19
Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Authors: Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs Wintraecken

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

Abstract
The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in R^2 and on surfaces embedded in R^3 as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points P in a domain Omega equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of P to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in Omega under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.
Cite as

Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs Wintraecken. Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2017.19,
  author =	{Boissonnat, Jean-Daniel and Rouxel-Labb\'{e}, Mael and Wintraecken, Mathijs},
  title =	{{Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-72060},
  doi =		{10.4230/LIPIcs.SoCG.2017.19},
  annote =	{Keywords: Riemannian Geometry, Voronoi diagram, Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.642
Building Efficient and Compact Data Structures for Simplicial Complexes

Authors: Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas

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

Abstract
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.
Cite as

Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas. Building Efficient and Compact Data Structures for Simplicial Complexes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 642-657, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SOCG.2015.642,
  author =	{Boissonnat, Jean-Daniel and S., Karthik C. and Tavenas, S\'{e}bastien},
  title =	{{Building Efficient and Compact Data Structures for Simplicial Complexes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{642--657},
  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.642},
  URN =		{urn:nbn:de:0030-drops-50981},
  doi =		{10.4230/LIPIcs.SOCG.2015.642},
  annote =	{Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard}
}
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