Search Results

Documents authored by Lieutier, André

Document
DOI: 10.4230/LIPIcs.SoCG.2026.37
A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach

Authors: Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Assumptions on the reach are crucial for ensuring the correctness of many geometric and topological algorithms, including triangulation, manifold reconstruction and learning, homotopy reconstruction, and methods for estimating curvature or reach. However, these assumptions are often coupled with the requirement that the manifold be smooth, typically at least C². In this paper, we prove that any manifold with positive reach can be approximated arbitrarily well by a C^∞ manifold without significantly reducing the reach. More precisely, given a manifold with reach R, we construct a manifold that is ε-close to it in the C¹ sense (both the manifold and its tangent spaces are close), and has reach at least R-ε. The proof employs techniques from differential topology - partitions of unity and smoothing using convolution kernels. This result implies that nearly all theorems established for C² or manifolds with a certain reach naturally extend to manifolds with the same reach, even if they are not C², for free!
Cite as

Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken. A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalpozkourimska_et_al:LIPIcs.SoCG.2026.37,
  author =	{Dal Poz Kou\v{r}imsk\'{a}, Hana and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.37},
  URN =		{urn:nbn:de:0030-drops-258434},
  doi =		{10.4230/LIPIcs.SoCG.2026.37},
  annote =	{Keywords: Reach, Manifolds, Smoothing, Differentiability, Differential topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.74
Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach

Authors: André Lieutier and Mathijs Wintraecken

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
This paper contains three main results. Firstly, we give an elementary proof of the following statement: Let ℳ be a topological manifold without boundary embedded in R^d. If ℳ has positive reach, then ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space. Conversely if ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space, then ℳ has positive reach. The result was hinted at by Federer when he introduced the reach, and proved by Lytchak. Lytchak’s proof relies heavily on CAT(k)-theory. The proof presented here uses only basic results on homology. Secondly, we give optimal Lipschitz-constants for the derivative, in other words we give an optimal bound for the angle between tangent spaces in term of the distance between the points. We stress that Lytchak did not provide any bound, let alone an optimal one, making his proof, although interesting from a mathematical perspective, ineffectual in an algorithmic setting. To provide precise and optimal bounds on the angle between tangent spaces, we formally introduce the local reach for sets of positive reach, based on Aamari et al.’s discussion for C² manifolds. We prove that the local reach of a manifold is completely characterized by the variation of tangent spaces. This improves earlier results, that were either suboptimal or assumed that the manifold was C². Thirdly, we show that the value of the reach is equals minimum of the local reach of the set and a global bottleneck for any set. This generalizes a result by Aamari et al. which explains how the reach is attained for C² manifolds.
Cite as

André Lieutier and Mathijs Wintraecken. Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lieutier_et_al:LIPIcs.SoCG.2026.74,
  author =	{Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{74:1--74:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.74},
  URN =		{urn:nbn:de:0030-drops-258812},
  doi =		{10.4230/LIPIcs.SoCG.2026.74},
  annote =	{Keywords: Reach, Manifolds, Differentiability class, Lipschitz continuity, Tangent space}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.75
Geodesics of Length Less Than πR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints

Authors: André Lieutier and Mathijs Wintraecken

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Positive reach underpins many results in computational geometry and topology. It is used for triangulation criteria, topological inference, and manifold learning. The geometric properties of these sets have therefore been studied intensely. Here we focus on the shortest paths or minimizing geodesics in these sets. Our main result states that minimizing geodesics of length strictly less than π R in a set of reach R are unique. This in turn implies that such minimizing geodesics are continuous with respect to the endpoints.
Cite as

André Lieutier and Mathijs Wintraecken. Geodesics of Length Less Than πR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 75:1-75:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lieutier_et_al:LIPIcs.SoCG.2026.75,
  author =	{Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{Geodesics of Length Less Than \piR in a Set of Reach R Are Unique and Continuous with Respect to the Endpoints}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{75:1--75:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.75},
  URN =		{urn:nbn:de:0030-drops-258823},
  doi =		{10.4230/LIPIcs.SoCG.2026.75},
  annote =	{Keywords: Reach, geodesics, metric geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.11
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds

Authors: Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier

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

Abstract
Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.
Cite as

Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier. When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2025.11,
  author =	{Attali, Dominique and Cl\'{e}mot, Matt\'{e}o and Dornelas, Bianca B. and Lieutier, Andr\'{e}},
  title =	{{When Alpha-Complexes Collapse onto Codimension-1 Submanifolds}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-231630},
  doi =		{10.4230/LIPIcs.SoCG.2025.11},
  annote =	{Keywords: Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.11
Tight Bounds for the Learning of Homotopy à la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds

Authors: Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken

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

Abstract
In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to 𝒮. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately.
Cite as

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Tight Bounds for the Learning of Homotopy à la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2024.11,
  author =	{Attali, Dominique and Dal Poz Kou\v{r}imsk\'{a}, Hana and Fillmore, Christopher and Ghosh, Ishika and Lieutier, Andr\'{e} and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{Tight Bounds for the Learning of Homotopy \`{a} la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{11:1--11:19},
  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.11},
  URN =		{urn:nbn:de:0030-drops-199565},
  doi =		{10.4230/LIPIcs.SoCG.2024.11},
  annote =	{Keywords: Homotopy, Inference, Sets of positive reach}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.69
The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms

Authors: Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken

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

Abstract
We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms.
Cite as

Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken. The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 69:1-69:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalpozkourimska_et_al:LIPIcs.SoCG.2024.69,
  author =	{Dal Poz Kou\v{r}imsk\'{a}, Hana and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{69:1--69:18},
  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.69},
  URN =		{urn:nbn:de:0030-drops-200149},
  doi =		{10.4230/LIPIcs.SoCG.2024.69},
  annote =	{Keywords: Medial axis, Hausdorff distance, Lipschitz continuity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.87
The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition)

Authors: Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken

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

Abstract
In our companion paper "Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.
Cite as

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 87:1-87:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2024.87,
  author =	{Attali, Dominique and Dal Poz Kou\v{r}imsk\'{a}, Hana and Fillmore, Christopher and Ghosh, Ishika and Lieutier, Andr\'{e} and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{The Ultimate Frontier: An Optimality Construction for Homotopy Inference}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{87:1--87:6},
  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.87},
  URN =		{urn:nbn:de:0030-drops-200325},
  doi =		{10.4230/LIPIcs.SoCG.2024.87},
  annote =	{Keywords: Homotopy, Inference, Sets of positive reach}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.8
Delaunay-Like Triangulation of Smooth Orientable Submanifolds by 𝓁₁-Norm Minimization

Authors: Dominique Attali and André Lieutier

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

Abstract
In this paper, we focus on one particular instance of the shape reconstruction problem, in which the shape we wish to reconstruct is an orientable smooth submanifold of the Euclidean space. Assuming we have as input a simplicial complex K that approximates the submanifold (such as the Čech complex or the Rips complex), we recast the reconstruction problem as a 𝓁₁-norm minimization problem in which the optimization variable is a chain of K. Providing that K satisfies certain reasonable conditions, we prove that the considered minimization problem has a unique solution which triangulates the submanifold and coincides with the flat Delaunay complex introduced and studied in a companion paper [D. Attali and A. Lieutier, 2022]. Since the objective is a weighted 𝓁₁-norm and the contraints are linear, the triangulation process can thus be implemented by linear programming.
Cite as

Dominique Attali and André Lieutier. Delaunay-Like Triangulation of Smooth Orientable Submanifolds by 𝓁₁-Norm Minimization. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2022.8,
  author =	{Attali, Dominique and Lieutier, Andr\'{e}},
  title =	{{Delaunay-Like Triangulation of Smooth Orientable Submanifolds by 𝓁₁-Norm Minimization}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{8:1--8:16},
  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.8},
  URN =		{urn:nbn:de:0030-drops-160162},
  doi =		{10.4230/LIPIcs.SoCG.2022.8},
  annote =	{Keywords: manifold reconstruction, Delaunay complex, triangulation, sampling conditions, optimization, 𝓁₁-norm minimization, simplicial complex, chain, fundamental class}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.32
Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Authors: David Cohen-Steiner, André Lieutier, and Julien Vuillamy

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

Abstract
This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the general case. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.
Cite as

David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohensteiner_et_al:LIPIcs.SoCG.2020.32,
  author =	{Cohen-Steiner, David and Lieutier, Andr\'{e} and Vuillamy, Julien},
  title =	{{Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-121908},
  doi =		{10.4230/LIPIcs.SoCG.2020.32},
  annote =	{Keywords: OHCP, simplicial homology, triangulation, Delaunay}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.11
When Convexity Helps Collapsing Complexes

Authors: Dominique Attali, André Lieutier, and David Salinas

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

Abstract
This paper illustrates how convexity hypotheses help collapsing simplicial complexes. We first consider a collection of compact convex sets and show that the nerve of the collection is collapsible whenever the union of sets in the collection is convex. We apply this result to prove that the Delaunay complex of a finite point set is collapsible. We then consider a convex domain defined as the convex hull of a finite point set. We show that if the point set samples sufficiently densely the domain, then both the Cech complex and the Rips complex of the point set are collapsible for a well-chosen scale parameter. A key ingredient in our proofs consists in building a filtration by sweeping space with a growing sphere whose center has been fixed and studying events occurring through the filtration. Since the filtration mimics the sublevel sets of a Morse function with a single critical point, we anticipate this work to lay the foundations for a non-smooth, discrete Morse Theory.
Cite as

Dominique Attali, André Lieutier, and David Salinas. When Convexity Helps Collapsing Complexes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2019.11,
  author =	{Attali, Dominique and Lieutier, Andr\'{e} and Salinas, David},
  title =	{{When Convexity Helps Collapsing Complexes}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-104152},
  doi =		{10.4230/LIPIcs.SoCG.2019.11},
  annote =	{Keywords: collapsibility, convexity, collection of compact convex sets, nerve, filtration, Delaunay complex, Cech complex, Rips complex}
}
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}
}
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