Search Results

Documents authored by Wintraecken, Mathijs

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
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2022.66
A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition)

Authors: Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, and Mathijs Wintraecken

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

Abstract
The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.
Cite as

Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, and Mathijs Wintraecken. A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2022.66,
  author =	{Chambers, Erin and Fillmore, Christopher and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{A Cautionary Tale: Burning the Medial Axis Is Unstable}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{66:1--66:9},
  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.66},
  URN =		{urn:nbn:de:0030-drops-160744},
  doi =		{10.4230/LIPIcs.SoCG.2022.66},
  annote =	{Keywords: Medial axis, Collapse, Pruning, Burning, Stability}
}
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.2021.32
The Density Fingerprint of a Periodic Point Set

Authors: Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken

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

Abstract
Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness in the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.
Cite as

Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2021.32,
  author =	{Edelsbrunner, Herbert and Heiss, Teresa and Kurlin, Vitaliy and Smith, Philip and Wintraecken, Mathijs},
  title =	{{The Density Fingerprint of a Periodic Point Set}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{32:1--32: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.32},
  URN =		{urn:nbn:de:0030-drops-138310},
  doi =		{10.4230/LIPIcs.SoCG.2021.32},
  annote =	{Keywords: Lattices, periodic sets, isometries, Dirichlet-Voronoi domains, Brillouin zones, bottleneck distance, stability, continuity, crystal database}
}
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.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.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.255
Riemannian Simplices and Triangulations

Authors: Ramsay Dyer, Gert Vegter, and Mathijs Wintraecken

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

Abstract
We study a natural intrinsic definition of geometric simplices in Riemannian manifolds of arbitrary finite dimension, and exploit these simplices to obtain criteria for triangulating compact Riemannian manifolds. These geometric simplices are defined using Karcher means. Given a finite set of vertices in a convex set on the manifold, the point that minimises the weighted sum of squared distances to the vertices is the Karcher mean relative to the weights. Using barycentric coordinates as the weights, we obtain a smooth map from the standard Euclidean simplex to the manifold. A Riemannian simplex is defined as the image of the standard simplex under this barycentric coordinate map. In this work we articulate criteria that guarantee that the barycentric coordinate map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate. Quality measures for the "thickness" or "fatness" of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However, when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the absolute values of the sectional curvatures of the manifold. An analysis of the geometry of non-degenerate Riemannian simplices leads to conditions which guarantee that a simplicial complex is homeomorphic to the manifold.
Cite as

Ramsay Dyer, Gert Vegter, and Mathijs Wintraecken. Riemannian Simplices and Triangulations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 255-269, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:LIPIcs.SOCG.2015.255,
  author =	{Dyer, Ramsay and Vegter, Gert and Wintraecken, Mathijs},
  title =	{{Riemannian Simplices and Triangulations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{255--269},
  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.255},
  URN =		{urn:nbn:de:0030-drops-51361},
  doi =		{10.4230/LIPIcs.SOCG.2015.255},
  annote =	{Keywords: Karcher means, barycentric coordinates, triangulation, Riemannian manifold, Riemannian simplices}
}
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