---
OA_place: repository
OA_type: green
_id: '21056'
abstract:
- lang: eng
text: "In this work, we introduce and study what we believe is an intriguing, and,
to the best of our knowledge, previously unknown connection between two fundamental
areas in computational topology, namely topological data analysis (TDA) and knot
theory. Given a function from a topological space to ℝ, TDA provides tools to
simplify and study the importance of topological features: in particular, the
\U0001D459^\U0001D461ℎ-dimensional persistence diagram encodes the topological
changes (or \U0001D459-homology) in the sublevel set as the function value increases
into a set of points in the plane. Given a continuous one parameter family of
such functions, we can combine the persistence diagrams into an object known as
a vineyard, which tracks the evolution of points in the persistence diagram as
the function changes. If we further restrict that family of functions to be periodic,
we identify the two ends of the vineyard, yielding a closed vineyard. This allows
the study of monodromy, which in this context means that following the family
of functions for a period permutes the set of points in a non-trivial way. Recent
work has studied monodromy in the directional persistent homology transform, demonstrating
some interesting connections between an input shape and monodromy in the persistent
homology transform for 0-dimensional homology embedded in ℝ^2.\r\nIn this work,
given a link and a value \U0001D459, we construct a topological space (based on
the given link) and periodic family of functions on this space (based on the Euclidean
distance function), such that the closed \U0001D459-vineyard contains this link.
This shows that vineyards are topologically as rich as one could possibly hope,
suggesting many future directions of work. Importantly, it has at least two immediate
consequences we explicitly point out:\r\n1.\tMonodromy of any periodicity can
occur in a \U0001D459-vineyard for any \U0001D459. This answers a variant of a
question by Arya and collaborators. To exhibit this as a consequence of our first
main result we also reformulate monodromy in a more geometric way, which may be
of interest in itself.\r\n2.\tTopologically distinguishing closed vineyards is
likely to be difficult (from a complexity theory as well as from a practical perspective)
because of the difficulty of knot and link recognition, which have strong connections
to many NP-hard problems."
acknowledgement: We thank the reviewers for both SODA and ATMCS for their comments,
whichimproved the exposition. We thank Kate Turner for discussion and Clément Maria
for pointing out thatAlexander’s theorem was already (well) known. Mathijs Wintraecken
would like to express his gratitude tothe administrative support he received from
University of Notre Dame during his visit and from Sophie Honnoratand Stephanie
Verdonck at Inria in general.This work has been supported by the ANR grant StratMesh,
ANR-24-CE48-1899, by NSF award 2444309, andthe welcome package from IDEX of the
Université Côte d’Azur, ANR-15-IDEX-01.
article_processing_charge: No
arxiv: 1
author:
- first_name: Erin W.
full_name: Chambers, Erin W.
last_name: Chambers
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. Braiding Vineyards.
In: Green Larsen K, Saha B, eds. Proceedings of the 2026 Annual ACM-SIAM Symposium
on Discrete Algorithms. Philadelphia, PA, United States: Society for Industrial
and Applied Mathematics; 2026:6240-6263. doi:10.1137/1.9781611978971.225'
apa: 'Chambers, E. W., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M.
(2026). Braiding Vineyards. In K. Green Larsen & B. Saha (Eds.), Proceedings
of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 6240–6263).
Philadelphia, PA, United States: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611978971.225'
chicago: 'Chambers, Erin W., Christopher D Fillmore, Elizabeth R Stephenson, and
Mathijs Wintraecken. “Braiding Vineyards.” In Proceedings of the 2026 Annual
ACM-SIAM Symposium on Discrete Algorithms, edited by Kasper Green Larsen and
Barna Saha, 6240–63. Philadelphia, PA, United States: Society for Industrial and
Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.225.'
ieee: 'E. W. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Braiding
Vineyards,” in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete
Algorithms, K. Green Larsen and B. Saha, Eds. Philadelphia, PA, United States:
Society for Industrial and Applied Mathematics, 2026, pp. 6240–6263.'
ista: 'Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. 2026.Braiding Vineyards.
In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms.
, 6240–6263.'
mla: Chambers, Erin W., et al. “Braiding Vineyards.” Proceedings of the 2026
Annual ACM-SIAM Symposium on Discrete Algorithms, edited by Kasper Green Larsen
and Barna Saha, Society for Industrial and Applied Mathematics, 2026, pp. 6240–63,
doi:10.1137/1.9781611978971.225.
short: E.W. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, K. Green
Larsen, B. Saha (Eds.), Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA,
United States, 2026, pp. 6240–6263.
date_created: 2026-01-28T12:58:16Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-02-16T08:06:23Z
day: '07'
department:
- _id: HeEd
doi: 10.1137/1.9781611978971.225
editor:
- first_name: Kasper
full_name: Green Larsen, Kasper
last_name: Green Larsen
- first_name: Barna
full_name: Saha, Barna
last_name: Saha
external_id:
arxiv:
- '2504.11203'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2504.11203
month: '01'
oa: 1
oa_version: Preprint
page: 6240-6263
place: Philadelphia, PA, United States
publication: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611978971'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '21051'
relation: earlier_version
status: public
status: public
title: Braiding Vineyards
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: repository
_id: '21051'
abstract:
- lang: eng
text: 'In this work, we introduce and study what we believe is an intriguing and,
to the best of our knowledge, previously unknown connection between two areas
in computational topology, topological data analysis (TDA) and knot theory. Given
a function from a topological space to $\mathbb{R}$, TDA provides tools to simplify
and study the importance of topological features: in particular, the $l^{th}$-dimensional
persistence diagram encodes the $l$-homology in the sublevel set as the function
value increases as a set of points in the plane. Given a continuous one-parameter
family of such functions, we can combine the persistence diagrams into an object
known as a vineyard, which track the evolution of points in the persistence diagram.
If we further restrict that family of functions to be periodic, we identify the
two ends of the vineyard, yielding a closed vineyard. This allows the study of
monodromy, which in this context means that following the family of functions
for a period permutes the set of points in a non-trivial way. In this work, given
a link and value $l$, we construct a topological space and periodic family of
functions such that the closed $l$-vineyard contains this link. This shows that
vineyards are topologically as rich as one could possibly hope. Importantly, it
has at least two immediate consequences: First, monodromy of any periodicity can
occur in a $l$-vineyard, answering a variant of a question by [Arya et al 2024].
To exhibit this, we also reformulate monodromy in a more geometric way, which
may be of interest in itself. Second, distinguishing vineyards is likely to be
difficult given the known difficulty of knot and link recognition, which have
strong connections to many NP-hard problems.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Erin
full_name: ' Chambers, Erin'
last_name: ' Chambers'
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. Braiding vineyards.
arXiv. doi:10.48550/ARXIV.2504.11203
apa: Chambers, E., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M. (n.d.).
Braiding vineyards. arXiv. https://doi.org/10.48550/ARXIV.2504.11203
chicago: Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs
Wintraecken. “Braiding Vineyards.” ArXiv, n.d. https://doi.org/10.48550/ARXIV.2504.11203.
ieee: E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Braiding
vineyards,” arXiv. .
ista: Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. Braiding vineyards.
arXiv, 10.48550/ARXIV.2504.11203.
mla: Chambers, Erin, et al. “Braiding Vineyards.” ArXiv, doi:10.48550/ARXIV.2504.11203.
short: E. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, ArXiv (n.d.).
corr_author: '1'
date_created: 2026-01-27T14:41:44Z
date_published: 2026-01-02T00:00:00Z
date_updated: 2026-04-07T11:42:48Z
day: '02'
department:
- _id: HeEd
doi: 10.48550/ARXIV.2504.11203
external_id:
arxiv:
- '2504.11203'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2504.11203
month: '01'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
record:
- id: '21056'
relation: later_version
status: public
- id: '21021'
relation: dissertation_contains
status: public
status: public
title: Braiding vineyards
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: preprint
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20260'
abstract:
- lang: eng
text: The medial axis of a set consists of the points in the ambient space without
a unique closest point in the original set. Since its introduction, the medial
axis has been used extensively in many applications as a method of computing a
skeleton topologically equivalent to the original set. 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 in the computational
geometry community. 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, we demonstrate an isotopy of
a shape where the medial axis goes from collapsible to non-collapsible. More precisely,
we consider the standard deformation retract from the closed ball to Bing’s house
with two rooms, but stop just short of the point where Bing’s house becomes two
dimensional. This way we obtain an isotopy from the 3-ball to a thickened version
of Bing’s house. Under this isotopy, the medial axis goes from collapsible to
non-collapsible. We stress that this isotopy can be made generic, in the sense
of singularity theory, as developed by Arnol’d and Thom.
acknowledgement: "We thank André Lieutier, David Letscher, Ellen Gasparovic, Kathryn
Leonard, and Tao Ju for early discussions on this work. We also thank Lu Liu, Yajie
Yan, and Tao Ju for sharing code to generate the examples. We further thank Abigail
Thompson for discussion on the conjecture and James Damon for sharing his insight
in singularity theory. We thank the reviewers for their detailed reviews, which
helped to improve the exposition.\r\nOpen access funding provided by Institute of
Science and Technology (IST Austria). Partially supported by the DFG Collaborative
Research Center TRR 109, ‘Discretization in Geometry and Dynamics’ and the European
Research Council (ERC), grant no. 788183, ‘Alpha Shape Theory Extended’. The first
author was supported in part by the National Science Foundation through grants DBI-1759807,
CCF-1907612, and CCF-2444309. The fourth author was supported by the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
grant agreement No. 754411, the Austrian science fund (FWF) M-3073, ANR grant StratMesh,
ANR-24-CE48-1899, and the welcome package from IDEX of the Université Côte d’Azur,
ANR-15-IDEX-01."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Erin Wolf
full_name: Chambers, Erin Wolf
last_name: Chambers
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. Burning or collapsing
the medial axis is unstable. La Matematica. 2025;4:811-828. doi:10.1007/s44007-025-00170-0
apa: Chambers, E. W., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M.
(2025). Burning or collapsing the medial axis is unstable. La Matematica.
Springer Nature. https://doi.org/10.1007/s44007-025-00170-0
chicago: Chambers, Erin Wolf, Christopher D Fillmore, Elizabeth R Stephenson, and
Mathijs Wintraecken. “Burning or Collapsing the Medial Axis Is Unstable.” La
Matematica. Springer Nature, 2025. https://doi.org/10.1007/s44007-025-00170-0.
ieee: E. W. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Burning
or collapsing the medial axis is unstable,” La Matematica, vol. 4. Springer
Nature, pp. 811–828, 2025.
ista: Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. 2025. Burning or collapsing
the medial axis is unstable. La Matematica. 4, 811–828.
mla: Chambers, Erin Wolf, et al. “Burning or Collapsing the Medial Axis Is Unstable.”
La Matematica, vol. 4, Springer Nature, 2025, pp. 811–28, doi:10.1007/s44007-025-00170-0.
short: E.W. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, La Matematica
4 (2025) 811–828.
corr_author: '1'
date_created: 2025-08-31T22:01:33Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2026-04-07T11:42:48Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s44007-025-00170-0
ec_funded: 1
file:
- access_level: open_access
checksum: e2043259194bfcdf3d74c4da8a5a853f
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T07:52:58Z
date_updated: 2025-12-30T07:52:58Z
file_id: '20885'
file_name: 2025_LaMatematica_Chambers.pdf
file_size: 2678640
relation: main_file
success: 1
file_date_updated: 2025-12-30T07:52:58Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 811-828
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: La Matematica
publication_identifier:
eissn:
- 2730-9657
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21021'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Burning or collapsing the medial axis is unstable
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2025'
...
---
_id: '18097'
abstract:
- lang: eng
text: "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 \U0001D4AE (either manifold or general set with positive
reach) such that one can infer the homotopy of \U0001D4AE 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."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I02979-N35. Mathijs Wintraecken: Supported by the
European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant
No. M-3073, and the welcome package from IDEX of the Université Côte d’Azur.\r\nWe
thank Jean-Daniel Boissonnat, Herbert Edelsbrunner, and Mariette Yvinec for discussion."
alternative_title:
- LIPIcs
article_number: '87'
article_processing_charge: Yes
author:
- first_name: Dominique
full_name: Attali, Dominique
last_name: Attali
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Ishika
full_name: Ghosh, Ishika
id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff
last_name: Ghosh
- first_name: Andre
full_name: Lieutier, Andre
last_name: Lieutier
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Attali D, Kourimska H, Fillmore CD, et al. The ultimate frontier: An optimality
construction for homotopy inference (media exposition). In: 40th International
Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.87'
apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson,
E. R., & Wintraecken, M. (2024). The ultimate frontier: An optimality construction
for homotopy inference (media exposition). In 40th International Symposium
on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.87'
chicago: 'Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh,
Andre Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “The Ultimate
Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).”
In 40th International Symposium on Computational Geometry, Vol. 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.87.'
ieee: 'D. Attali et al., “The ultimate frontier: An optimality construction
for homotopy inference (media exposition),” in 40th International Symposium
on Computational Geometry, Athens, Greece, 2024, vol. 293.'
ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken
M. 2024. The ultimate frontier: An optimality construction for homotopy inference
(media exposition). 40th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 293, 87.'
mla: 'Attali, Dominique, et al. “The Ultimate Frontier: An Optimality Construction
for Homotopy Inference (Media Exposition).” 40th International Symposium on
Computational Geometry, vol. 293, 87, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.87.'
short: D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson,
M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
corr_author: '1'
date_created: 2024-09-19T10:29:48Z
date_published: 2024-06-06T00:00:00Z
date_updated: 2025-04-15T07:16:58Z
day: '06'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.87
ec_funded: 1
file:
- access_level: open_access
checksum: 9355c2e60b8ec285e1b22719c5b73f1a
content_type: application/pdf
creator: dernst
date_created: 2024-09-19T10:30:37Z
date_updated: 2024-09-19T10:30:37Z
file_id: '18098'
file_name: 2024_LIPICs_Attali.pdf
file_size: 3507177
relation: main_file
success: 1
file_date_updated: 2024-09-19T10:30:37Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'The ultimate frontier: An optimality construction for homotopy inference (media
exposition)'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17144'
abstract:
- lang: eng
text: "We prove that the medial axis of closed sets is Hausdorff stable in the following
sense: Let \U0001D4AE ⊆ ℝ^d be a fixed closed set that contains a bounding sphere.
That is, the bounding sphere is part of the set \U0001D4AE. 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(\U0001D4AE), 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."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I 02979-N35.\r\nSupported by the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and
the welcome package from IDEX of the Université Cô d'Azur.\r\nWe are greatly indebted
to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher
Fillmore, and Elizabeth Stephenson for early discussions and all members of the
Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape
team (Inria) for the atmosphere in which this research was conducted."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: No
arxiv: 1
author:
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Kourimska H, Lieutier A, Wintraecken M. 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. Vol 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.69'
apa: 'Kourimska, H., Lieutier, A., & Wintraecken, M. (2024). 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 (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.69'
chicago: Kourimska, Hana, 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, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.SoCG.2024.69.
ieee: H. Kourimska, A. Lieutier, and M. 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,
Athens, Greece, 2024, vol. 293.
ista: 'Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed
bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient
diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 293, 69.'
mla: Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz
Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.”
40th International Symposium on Computational Geometry, vol. 293, 69, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.69.
short: H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium
on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-04-15T07:16:58Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.69
ec_funded: 1
external_id:
arxiv:
- '2212.01118'
file:
- access_level: open_access
checksum: b40ff456c19294adb5d9613fcfd751c6
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:33:40Z
date_updated: 2024-06-17T08:33:40Z
file_id: '17150'
file_name: 2024_LIPICS_Kourimska.pdf
file_size: 1612558
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:33:40Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The medial axis of any closed bounded set Is Lipschitz stable with respect
to the Hausdorff distance Under ambient diffeomorphisms
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17170'
abstract:
- lang: eng
text: "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) \U0001D4AE of positive reach may be noisy. We work with two one-sided
Hausdorff distances - ε and δ - between P and \U0001D4AE. 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
\U0001D4AE. 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."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I 02979-N35.\r\nWintraecken, Mathijs: Supported by
the European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant
No. M-3073, and the welcome package from IDEX of the Université Côte d'Azur."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Dominique
full_name: Attali, Dominique
last_name: Attali
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Ishika
full_name: Ghosh, Ishika
id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff
last_name: Ghosh
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Attali D, Kourimska H, Fillmore CD, et al. 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. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19.
doi:10.4230/LIPIcs.SoCG.2024.11'
apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson,
E. R., & Wintraecken, M. (2024). 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 (Vol.
293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2024.11'
chicago: Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh,
André Lieutier, Elizabeth R 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, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.11.
ieee: D. Attali et al., “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, Athens, Greece,
2024, vol. 293, p. 11:1-11:19.
ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken
M. 2024. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
for subsets of euclidean spaces and of Riemannian manifolds. 40th International
Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 293, 11:1-11:19.'
mla: Attali, Dominique, et al. “Tight Bounds for the Learning of Homotopy à La Niyogi,
Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.”
40th International Symposium on Computational Geometry, vol. 293, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:10.4230/LIPIcs.SoCG.2024.11.
short: D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson,
M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
date_created: 2024-06-25T11:45:58Z
date_published: 2024-06-06T00:00:00Z
date_updated: 2025-04-15T07:16:57Z
day: '06'
ddc:
- '516'
department:
- _id: GradSch
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.11
ec_funded: 1
external_id:
arxiv:
- '2206.10485'
file:
- access_level: open_access
checksum: 6a2ddc8b51aa58f197a8b294750f1f8d
content_type: application/pdf
creator: cfillmor
date_created: 2024-06-25T11:47:26Z
date_updated: 2024-06-25T11:47:26Z
file_id: '17171'
file_name: LIPIcs.SoCG.2024.11.pdf
file_size: 20886142
relation: main_file
success: 1
file_date_updated: 2024-06-25T11:47:26Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 11:1-11:19
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959773164'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
for subsets of euclidean spaces and of Riemannian manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17190'
abstract:
- lang: eng
text: "For a locally finite set, \U0001D434⊆ℝ\U0001D451\r\n, the \U0001D458\r\nth
Brillouin zone of \U0001D44E∈\U0001D434\r\n is the region of points \U0001D465∈ℝ\U0001D451\r\n
for which ‖\U0001D465−\U0001D44E‖\r\n is the \U0001D458\r\nth smallest among the
Euclidean distances between \U0001D465\r\n and the points in \U0001D434\r\n. If
\U0001D434\r\n is a lattice, the \U0001D458\r\nth Brillouin zones of the points
in \U0001D434\r\n are translates of each other, and together they tile space.
Depending on the value of \U0001D458\r\n, they express medium- or long-range order
in the set. We study fundamental geometric and combinatorial properties of Brillouin
zones, focusing on the integer lattice and its perturbations. Our results include
the stability of a Brillouin zone under perturbations, a linear upper bound on
the number of chambers in a zone for lattices in ℝ2\r\n, and the convergence of
the maximum volume of a chamber to zero for the integer lattice."
acknowledgement: The second author is partially supported by the Alexander von Humboldt
Foundation. The sixth author is supported by the European Union's Horizon 2020 research
and innovation programme under Marie Sklodowska-Curie grant agreement 754411, and
by Austrian Science Fund(FWF) grant M-3073. All other authors are supported by European
Research Council (ERC) grant 788183, by the Wittgenstein Prize, by Austrian Science
Fund (FWF) grant Z 342-N31, and by the DFG Collaborative Research Center TRR 109,
Austrian Science Fund (FWF) grant I 02979-N35.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Alexey
full_name: Garber, Alexey
last_name: Garber
- first_name: Mohadese
full_name: Ghafaris, Mohadese
last_name: Ghafaris
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Morteza
full_name: Saghafiant, Morteza
last_name: Saghafiant
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M.
Brillouin zones of integer lattices and their perturbations. SIAM Journal on
Discrete Mathematics. 2024;38(2):1784-1807. doi:10.1137/22M1489071
apa: Edelsbrunner, H., Garber, A., Ghafaris, M., Heiss, T., Saghafiant, M., &
Wintraecken, M. (2024). Brillouin zones of integer lattices and their perturbations.
SIAM Journal on Discrete Mathematics. Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/22M1489071
chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafaris, Teresa Heiss,
Morteza Saghafiant, and Mathijs Wintraecken. “Brillouin Zones of Integer Lattices
and Their Perturbations.” SIAM Journal on Discrete Mathematics. Society
for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/22M1489071.
ieee: H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, and M. Wintraecken,
“Brillouin zones of integer lattices and their perturbations,” SIAM Journal
on Discrete Mathematics, vol. 38, no. 2. Society for Industrial and Applied
Mathematics, pp. 1784–1807, 2024.
ista: Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M.
2024. Brillouin zones of integer lattices and their perturbations. SIAM Journal
on Discrete Mathematics. 38(2), 1784–1807.
mla: Edelsbrunner, Herbert, et al. “Brillouin Zones of Integer Lattices and Their
Perturbations.” SIAM Journal on Discrete Mathematics, vol. 38, no. 2, Society
for Industrial and Applied Mathematics, 2024, pp. 1784–807, doi:10.1137/22M1489071.
short: H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, M. Wintraecken,
SIAM Journal on Discrete Mathematics 38 (2024) 1784–1807.
corr_author: '1'
date_created: 2024-06-30T22:01:05Z
date_published: 2024-06-07T00:00:00Z
date_updated: 2025-09-08T08:06:04Z
day: '07'
department:
- _id: HeEd
doi: 10.1137/22M1489071
ec_funded: 1
external_id:
arxiv:
- '2204.01077'
isi:
- '001292728600001'
intvolume: ' 38'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2204.01077
month: '06'
oa: 1
oa_version: Preprint
page: 1784-1807
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
issn:
- 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Brillouin zones of integer lattices and their perturbations
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 38
year: '2024'
...
---
_id: '12287'
abstract:
- lang: eng
text: 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.
acknowledgement: "This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan
Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh
was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by
the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken
also received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian
Science Fund (FWF): M-3073. A part of the results described in this paper were presented
at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science
Fund (FWF)."
article_processing_charge: No
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- first_name: Arijit
full_name: Ghosh, Arijit
last_name: Ghosh
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 2023;69:156-191.
doi:10.1007/s00454-022-00431-7
apa: Boissonnat, J.-D., Dyer, R., Ghosh, A., & Wintraecken, M. (2023). Local
criteria for triangulating general manifolds. Discrete & Computational
Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00431-7
chicago: Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken.
“Local Criteria for Triangulating General Manifolds.” Discrete & Computational
Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00431-7.
ieee: J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for
triangulating general manifolds,” Discrete & Computational Geometry,
vol. 69. Springer Nature, pp. 156–191, 2023.
ista: Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 69, 156–191.
mla: Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.”
Discrete & Computational Geometry, vol. 69, Springer Nature, 2023,
pp. 156–91, doi:10.1007/s00454-022-00431-7.
short: J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete & Computational
Geometry 69 (2023) 156–191.
corr_author: '1'
date_created: 2023-01-16T10:04:06Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2025-04-14T07:44:00Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-022-00431-7
ec_funded: 1
external_id:
isi:
- '000862193600001'
file:
- access_level: open_access
checksum: 46352e0ee71e460848f88685ca852681
content_type: application/pdf
creator: dernst
date_created: 2023-02-02T11:01:10Z
date_updated: 2023-02-02T11:01:10Z
file_id: '12488'
file_name: 2023_DiscreteCompGeometry_Boissonnat.pdf
file_size: 582850
relation: main_file
success: 1
file_date_updated: 2023-02-02T11:01:10Z
has_accepted_license: '1'
intvolume: ' 69'
isi: 1
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 156-191
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local criteria for triangulating general manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 69
year: '2023'
...
---
_id: '12763'
abstract:
- lang: eng
text: 'Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift
176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended
the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets
S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert
showed that sets of positive reach in Euclidean space and Riemannian manifolds
are very similar. In this paper we introduce a slight variant of Kleinjohann’s
and Bangert’s extension and quantify the similarity between sets of positive reach
in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we
bound the local feature size (a local version of the reach) of its lifting to
the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that
rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated
by the importance of the reach and local feature size to manifold learning, topological
inference, and triangulating manifolds and the fact that intrinsic approaches
circumvent the curse of dimensionality.'
acknowledgement: "We thank Eddie Aamari, David Cohen-Steiner, Isa Costantini, Fred
Chazal, Ramsay Dyer, André Lieutier, and Alef Sterk for discussion and Pierre Pansu
for encouragement. We further acknowledge the anonymous reviewers whose comments
helped improve the exposition.\r\nThe research leading to these results has received
funding from the European Research Council (ERC) under the European Union’s Seventh
Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic
Foundations of Geometry Understanding in Higher Dimensions). The first author is
further supported by the French government, through the 3IA Côte d’Azur Investments
in the Future project managed by the National Research Agency (ANR) with the reference
number ANR-19-P3IA-0002. The second author is supported by the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
Grant Agreement No. 754411 and the Austrian science fund (FWF) M-3073."
article_processing_charge: No
article_type: original
author:
- first_name: Jean Daniel
full_name: Boissonnat, Jean Daniel
last_name: Boissonnat
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat JD, Wintraecken M. The reach of subsets of manifolds. Journal
of Applied and Computational Topology. 2023;7:619-641. doi:10.1007/s41468-023-00116-x
apa: Boissonnat, J. D., & Wintraecken, M. (2023). The reach of subsets of manifolds.
Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-023-00116-x
chicago: Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets
of Manifolds.” Journal of Applied and Computational Topology. Springer
Nature, 2023. https://doi.org/10.1007/s41468-023-00116-x.
ieee: J. D. Boissonnat and M. Wintraecken, “The reach of subsets of manifolds,”
Journal of Applied and Computational Topology, vol. 7. Springer Nature,
pp. 619–641, 2023.
ista: Boissonnat JD, Wintraecken M. 2023. The reach of subsets of manifolds. Journal
of Applied and Computational Topology. 7, 619–641.
mla: Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of
Manifolds.” Journal of Applied and Computational Topology, vol. 7, Springer
Nature, 2023, pp. 619–41, doi:10.1007/s41468-023-00116-x.
short: J.D. Boissonnat, M. Wintraecken, Journal of Applied and Computational Topology
7 (2023) 619–641.
corr_author: '1'
date_created: 2023-03-26T22:01:08Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-04-14T07:44:01Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s41468-023-00116-x
ec_funded: 1
intvolume: ' 7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://inserm.hal.science/INRIA-SACLAY/hal-04083524v1
month: '09'
oa: 1
oa_version: Submitted Version
page: 619-641
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The reach of subsets of manifolds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2023'
...
---
_id: '12960'
abstract:
- lang: eng
text: "Isomanifolds are the generalization of isosurfaces to arbitrary dimension
and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate
multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the
manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider
its piecewise linear (PL) approximation M^\r\n based on a triangulation T of the
ambient space Rd. 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 δ=Ω(d2.5), M^ is O(D2)-close and
isotopic to M\r\n, 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. "
acknowledgement: The authors have received funding from the European Research Council
under the European Union's ERC grant greement 339025 GUDHI (Algorithmic Foundations
of Geometric Un-derstanding in Higher Dimensions). The first author was supported by the French government,through
the 3IA C\^ote d'Azur Investments in the Future project managed by the National
ResearchAgency (ANR) with the reference ANR-19-P3IA-0002. The third author was
supported by the Eu-ropean Union's Horizon 2020 research and innovation programme
under the Marie Sk\lodowska-Curiegrant agreement 754411 and the FWF (Austrian Science
Fund) grant M 3073.
article_processing_charge: No
article_type: original
author:
- first_name: Jean Daniel
full_name: Boissonnat, Jean Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in
time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal
on Computing. 2023;52(2):452-486. doi:10.1137/21M1412918
apa: Boissonnat, J. D., Kachanovich, S., & Wintraecken, M. (2023). Tracing isomanifolds
in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM
Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1412918
chicago: Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn
Triangulations.” SIAM Journal on Computing. Society for Industrial and
Applied Mathematics, 2023. https://doi.org/10.1137/21M1412918.
ieee: J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds
in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,”
SIAM Journal on Computing, vol. 52, no. 2. Society for Industrial and Applied
Mathematics, pp. 452–486, 2023.
ista: Boissonnat JD, Kachanovich S, Wintraecken M. 2023. Tracing isomanifolds in
Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM
Journal on Computing. 52(2), 452–486.
mla: Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial
in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing,
vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86,
doi:10.1137/21M1412918.
short: J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing
52 (2023) 452–486.
corr_author: '1'
date_created: 2023-05-14T22:01:00Z
date_published: 2023-04-30T00:00:00Z
date_updated: 2025-04-15T06:54:46Z
day: '30'
department:
- _id: HeEd
doi: 10.1137/21M1412918
ec_funded: 1
external_id:
isi:
- '001013183000012'
intvolume: ' 52'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1
month: '04'
oa: 1
oa_version: Submitted Version
page: 452-486
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '9441'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn
triangulations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...
---
_id: '13048'
abstract:
- lang: eng
text: In this paper we introduce a pruning of the medial axis called the (λ,α)-medial
axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff
sense under weak assumptions. More formally we prove that if K and K′ are close
in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as
metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is
1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff
distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲
dH(K,K′)1/2. These quantified stability results provide guarantees for practical
computations of medial axes from approximations. Moreover, they provide key ingredients
for studying the computability of the medial axis in the context of computable
analysis.
acknowledgement: "We are greatly indebted to Erin Chambers for posing a number of
questions that eventually led to this paper. We would also like to thank the other
organizers of the workshop on ‘Algorithms\r\nfor the medial axis’. We are also indebted
to Tatiana Ezubova for helping with the search for and translation of Russian literature.
The second author thanks all members of the Edelsbrunner and Datashape groups for
the atmosphere in which the research was conducted.\r\nThe research leading to these
results has received funding from the European Research Council (ERC) under the
European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement
No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions).
Supported by the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science
fund (FWF) M-3073."
article_processing_charge: No
arxiv: 1
author:
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Lieutier A, Wintraecken M. Hausdorff and Gromov-Hausdorff stable subsets of
the medial axis. In: Proceedings of the 55th Annual ACM Symposium on Theory
of Computing. Association for Computing Machinery; 2023:1768-1776. doi:10.1145/3564246.3585113'
apa: 'Lieutier, A., & Wintraecken, M. (2023). Hausdorff and Gromov-Hausdorff
stable subsets of the medial axis. In Proceedings of the 55th Annual ACM Symposium
on Theory of Computing (pp. 1768–1776). Orlando, FL, United States: Association
for Computing Machinery. https://doi.org/10.1145/3564246.3585113'
chicago: Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff
Stable Subsets of the Medial Axis.” In Proceedings of the 55th Annual ACM Symposium
on Theory of Computing, 1768–76. Association for Computing Machinery, 2023.
https://doi.org/10.1145/3564246.3585113.
ieee: A. Lieutier and M. Wintraecken, “Hausdorff and Gromov-Hausdorff stable subsets
of the medial axis,” in Proceedings of the 55th Annual ACM Symposium on Theory
of Computing, Orlando, FL, United States, 2023, pp. 1768–1776.
ista: 'Lieutier A, Wintraecken M. 2023. Hausdorff and Gromov-Hausdorff stable subsets
of the medial axis. Proceedings of the 55th Annual ACM Symposium on Theory of
Computing. STOC: Symposium on Theory of Computing, 1768–1776.'
mla: Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable
Subsets of the Medial Axis.” Proceedings of the 55th Annual ACM Symposium on
Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–76,
doi:10.1145/3564246.3585113.
short: A. Lieutier, M. Wintraecken, in:, Proceedings of the 55th Annual ACM Symposium
on Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–1776.
conference:
end_date: 2023-06-23
location: Orlando, FL, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2023-06-20
corr_author: '1'
date_created: 2023-05-22T08:02:02Z
date_published: 2023-06-02T00:00:00Z
date_updated: 2025-09-09T12:26:49Z
day: '02'
department:
- _id: HeEd
doi: 10.1145/3564246.3585113
ec_funded: 1
external_id:
arxiv:
- '2303.04014'
isi:
- '001064640700143'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2303.04014
month: '06'
oa: 1
oa_version: Preprint
page: 1768-1776
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9781450399135'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hausdorff and Gromov-Hausdorff stable subsets of the medial axis
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2023'
...
---
_id: '11428'
abstract:
- lang: eng
text: 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.
acknowledgement: 'Partially supported by the DFG Collaborative Research Center TRR
109, “Discretization in Geometry and Dynamics” and the European Research Council
(ERC), grant no. 788183, “Alpha Shape Theory Extended”. Erin Chambers: Supported
in part by the National Science Foundation through grants DBI-1759807, CCF-1907612,
and CCF-2106672. Mathijs Wintraecken: Supported by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No. 754411. The Austrian science fund (FWF) M-3073 Acknowledgements We thank André
Lieutier, David Letscher, Ellen Gasparovic, Kathryn Leonard, and Tao Ju for early
discussions on this work. We also thank Lu Liu, Yajie Yan and Tao Ju for sharing
code to generate the examples.'
article_processing_charge: No
author:
- first_name: Erin
full_name: Chambers, Erin
last_name: Chambers
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. A cautionary tale:
Burning the medial axis is unstable. In: Goaoc X, Kerber M, eds. 38th International
Symposium on Computational Geometry. Vol 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022:66:1-66:9. doi:10.4230/LIPIcs.SoCG.2022.66'
apa: 'Chambers, E., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M. (2022).
A cautionary tale: Burning the medial axis is unstable. In X. Goaoc & M. Kerber
(Eds.), 38th International Symposium on Computational Geometry (Vol. 224,
p. 66:1-66:9). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2022.66'
chicago: 'Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs
Wintraecken. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” In 38th
International Symposium on Computational Geometry, edited by Xavier Goaoc
and Michael Kerber, 224:66:1-66:9. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SoCG.2022.66.'
ieee: 'E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “A cautionary
tale: Burning the medial axis is unstable,” in 38th International Symposium
on Computational Geometry, Berlin, Germany, 2022, vol. 224, p. 66:1-66:9.'
ista: 'Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. 2022. A cautionary
tale: Burning the medial axis is unstable. 38th International Symposium on Computational
Geometry. SoCG: Symposium on Computational GeometryLIPIcs vol. 224, 66:1-66:9.'
mla: 'Chambers, Erin, et al. “A Cautionary Tale: Burning the Medial Axis Is Unstable.”
38th International Symposium on Computational Geometry, edited by Xavier
Goaoc and Michael Kerber, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, p. 66:1-66:9, doi:10.4230/LIPIcs.SoCG.2022.66.'
short: E. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, X. Goaoc,
M. Kerber (Eds.), 38th International Symposium on Computational Geometry, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9.
conference:
end_date: 2022-06-10
location: Berlin, Germany
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2022-06-07
corr_author: '1'
date_created: 2022-06-01T14:18:04Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2025-04-14T07:43:57Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2022.66
ec_funded: 1
editor:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
file:
- access_level: open_access
checksum: b25ce40fade4ebc0bcaae176db4f5f1f
content_type: application/pdf
creator: dernst
date_created: 2022-06-07T07:58:30Z
date_updated: 2022-06-07T07:58:30Z
file_id: '11437'
file_name: 2022_LIPICs_Chambers.pdf
file_size: 17580705
relation: main_file
success: 1
file_date_updated: 2022-06-07T07:58:30Z
has_accepted_license: '1'
intvolume: ' 224'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 66:1-66:9
project:
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 38th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-227-3
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
series_title: LIPIcs
status: public
title: 'A cautionary tale: Burning the medial axis is unstable'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 224
year: '2022'
...
---
_id: '9649'
abstract:
- lang: eng
text: "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 : Rd → Rd−n. A natural (and efficient) way to approximate an
isomanifold is to consider its Piecewise-Linear (PL) approximation based on a
triangulation T of the ambient space Rd. 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\r\nfine triangulation T . 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."
acknowledgement: "First and foremost, we acknowledge Siargey Kachanovich for discussions.
We thank Herbert Edelsbrunner and all members of his group, all former and current
members of the Datashape team (formerly known as Geometrica), and André Lieutier
for encouragement. We further thank the reviewers of Foundations of Computational
Mathematics and the reviewers and program committee of the Symposium on Computational
Geometry for their feedback, which improved the exposition.\r\nThis work was funded
by the European Research Council under the European Union’s ERC Grant Agreement
number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher
Dimensions). This work was also supported by the French government, through the
3IA Côte d’Azur Investments in the Future project managed by the National Research
Agency (ANR) with the reference number ANR-19-P3IA-0002. Mathijs Wintraecken also
received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement no. 754411."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat J-D, Wintraecken M. The topological correctness of PL approximations
of isomanifolds. Foundations of Computational Mathematics . 2022;22:967-1012.
doi:10.1007/s10208-021-09520-0
apa: Boissonnat, J.-D., & Wintraecken, M. (2022). The topological correctness
of PL approximations of isomanifolds. Foundations of Computational Mathematics
. Springer Nature. https://doi.org/10.1007/s10208-021-09520-0
chicago: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL Approximations of Isomanifolds.” Foundations of Computational Mathematics
. Springer Nature, 2022. https://doi.org/10.1007/s10208-021-09520-0.
ieee: J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL approximations
of isomanifolds,” Foundations of Computational Mathematics , vol. 22. Springer
Nature, pp. 967–1012, 2022.
ista: Boissonnat J-D, Wintraecken M. 2022. The topological correctness of PL approximations
of isomanifolds. Foundations of Computational Mathematics . 22, 967–1012.
mla: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL Approximations of Isomanifolds.” Foundations of Computational Mathematics
, vol. 22, Springer Nature, 2022, pp. 967–1012, doi:10.1007/s10208-021-09520-0.
short: J.-D. Boissonnat, M. Wintraecken, Foundations of Computational Mathematics 22
(2022) 967–1012.
corr_author: '1'
date_created: 2021-07-14T06:44:53Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2025-04-22T13:45:18Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s10208-021-09520-0
ec_funded: 1
external_id:
isi:
- '000673039600001'
file:
- access_level: open_access
checksum: f1d372ec3c08ec22e84f8e93e1126b8c
content_type: application/pdf
creator: mwintrae
date_created: 2021-07-14T06:44:36Z
date_updated: 2021-07-14T06:44:36Z
file_id: '9650'
file_name: Boissonnat-Wintraecken2021_Article_TheTopologicalCorrectnessOfPLA.pdf
file_size: 1455699
relation: main_file
file_date_updated: 2021-07-14T06:44:36Z
has_accepted_license: '1'
intvolume: ' 22'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 967-1012
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'Foundations of Computational Mathematics '
publication_identifier:
eissn:
- 1615-3383
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '7952'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The topological correctness of PL approximations of isomanifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2022'
...
---
_id: '8248'
abstract:
- lang: eng
text: 'We consider the following setting: suppose that we are given a manifold M
in Rd with positive reach. Moreover assume that we have an embedded simplical
complex A without boundary, whose vertex set lies on the manifold, is sufficiently
dense and such that all simplices in A have sufficient quality. We prove that
if, locally, interiors of the projection of the simplices onto the tangent space
do not intersect, then A is a triangulation of the manifold, that is, they are
homeomorphic.'
acknowledgement: "Open access funding provided by the Institute of Science and Technology
(IST Austria). Arijit Ghosh is supported by the Ramanujan Fellowship (No. SB/S2/RJN-064/2015),
India.\r\nThis work has been funded by the European Research Council under the European
Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric
Understanding in Higher Dimensions). The third author is supported by Ramanujan
Fellowship (No. SB/S2/RJN-064/2015), India. The fifth author also received funding
from the European Union’s Horizon 2020 research and innovation programme under the
Marie Skłodowska-Curie Grant Agreement No. 754411."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- first_name: Arijit
full_name: Ghosh, Arijit
last_name: Ghosh
- first_name: Andre
full_name: Lieutier, Andre
last_name: Lieutier
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. Local conditions
for triangulating submanifolds of Euclidean space. Discrete and Computational
Geometry. 2021;66:666-686. doi:10.1007/s00454-020-00233-9
apa: Boissonnat, J.-D., Dyer, R., Ghosh, A., Lieutier, A., & Wintraecken, M.
(2021). Local conditions for triangulating submanifolds of Euclidean space. Discrete
and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00233-9
chicago: Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, and
Mathijs Wintraecken. “Local Conditions for Triangulating Submanifolds of Euclidean
Space.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00233-9.
ieee: J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, and M. Wintraecken, “Local
conditions for triangulating submanifolds of Euclidean space,” Discrete and
Computational Geometry, vol. 66. Springer Nature, pp. 666–686, 2021.
ista: Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. 2021. Local conditions
for triangulating submanifolds of Euclidean space. Discrete and Computational
Geometry. 66, 666–686.
mla: Boissonnat, Jean-Daniel, et al. “Local Conditions for Triangulating Submanifolds
of Euclidean Space.” Discrete and Computational Geometry, vol. 66, Springer
Nature, 2021, pp. 666–86, doi:10.1007/s00454-020-00233-9.
short: J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, M. Wintraecken, Discrete
and Computational Geometry 66 (2021) 666–686.
corr_author: '1'
date_created: 2020-08-11T07:11:51Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2025-04-14T07:44:05Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00233-9
ec_funded: 1
external_id:
isi:
- '000558119300001'
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00454-020-00233-9
month: '09'
oa: 1
oa_version: Published Version
page: 666-686
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local conditions for triangulating submanifolds of Euclidean space
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2021'
...
---
_id: '8940'
abstract:
- lang: eng
text: We quantise Whitney’s construction to prove the existence of a triangulation
for any C^2 manifold, so that we get an algorithm with explicit bounds. We also
give a new elementary proof, which is completely geometric.
acknowledgement: This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). The third author also received
funding from the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding
provided by the Institute of Science and Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 2021;66(1):386-434. doi:10.1007/s00454-020-00250-8'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Triangulating
submanifolds: An elementary and quantified version of Whitney’s method. Discrete
& Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00250-8'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s
Method.” Discrete & Computational Geometry. Springer Nature, 2021.
https://doi.org/10.1007/s00454-020-00250-8.'
ieee: 'J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds:
An elementary and quantified version of Whitney’s method,” Discrete & Computational
Geometry, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.'
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 66(1), 386–434.'
mla: 'Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary
and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry,
vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:10.1007/s00454-020-00250-8.'
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational
Geometry 66 (2021) 386–434.
corr_author: '1'
date_created: 2020-12-12T11:07:02Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2025-04-14T07:43:50Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00250-8
ec_funded: 1
external_id:
isi:
- '000597770300001'
file:
- access_level: open_access
checksum: c848986091e56699dc12de85adb1e39c
content_type: application/pdf
creator: kschuh
date_created: 2021-08-06T09:52:29Z
date_updated: 2021-08-06T09:52:29Z
file_id: '9795'
file_name: 2021_DescreteCompGeopmetry_Boissonnat.pdf
file_size: 983307
relation: main_file
success: 1
file_date_updated: 2021-08-06T09:52:29Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '1'
keyword:
- Theoretical Computer Science
- Computational Theory and Mathematics
- Geometry and Topology
- Discrete Mathematics and Combinatorics
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 386-434
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Triangulating submanifolds: An elementary and quantified version of Whitney’s
method'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2021'
...
---
_id: '9441'
abstract:
- lang: eng
text: "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 \U0001D4AF
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. "
acknowledgement: We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent
Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge
the reviewers.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in
time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: 37th
International Symposium on Computational Geometry (SoCG 2021). Vol 189. Leibniz
International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:10.4230/LIPIcs.SoCG.2021.17'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Tracing
isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations.
In 37th International Symposium on Computational Geometry (SoCG 2021) (Vol.
189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.17'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn
Triangulations.” In 37th International Symposium on Computational Geometry
(SoCG 2021), 189:17:1-17:16. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.17.'
ieee: J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,”
in 37th International Symposium on Computational Geometry (SoCG 2021),
Virtual, 2021, vol. 189, p. 17:1-17:16.
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th
International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium
on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs),
LIPIcs, vol. 189, 17:1-17:16.'
mla: Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial
in d Using Coxeter-Freudenthal-Kuhn Triangulations.” 37th International Symposium
on Computational Geometry (SoCG 2021), vol. 189, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, p. 17:1-17:16, doi:10.4230/LIPIcs.SoCG.2021.17.
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International
Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, Dagstuhl, Germany, 2021, p. 17:1-17:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
date_created: 2021-06-02T10:10:55Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2025-04-15T07:09:18Z
day: '02'
ddc:
- '005'
- '516'
- '514'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.17
ec_funded: 1
file:
- access_level: open_access
checksum: c322aa48d5d35a35877896cc565705b6
content_type: application/pdf
creator: mwintrae
date_created: 2021-06-02T10:22:33Z
date_updated: 2021-06-02T10:22:33Z
file_id: '9442'
file_name: LIPIcs-SoCG-2021-17.pdf
file_size: 1972902
relation: main_file
success: 1
file_date_updated: 2021-06-02T10:22:33Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 17:1-17:16
place: Dagstuhl, Germany
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry (SoCG 2021)
publication_identifier:
isbn:
- 978-3-95977-184-9
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '12960'
relation: later_version
status: public
scopus_import: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn
triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '9345'
abstract:
- lang: eng
text: Modeling a crystal as a periodic point set, we present a fingerprint consisting
of density functionsthat facilitates the efficient search for new materials and
material properties. We prove invarianceunder isometries, continuity, and completeness
in the generic case, which are necessary featuresfor the reliable comparison of
crystals. The proof of continuity integrates methods from discretegeometry and
lattice theory, while the proof of generic completeness combines techniques fromgeometry
with analysis. The fingerprint has a fast algorithm based on Brillouin zones and
relatedinclusion-exclusion formulae. We have implemented the algorithm and describe
its application tocrystal structure prediction.
acknowledgement: The authors thank Janos Pach for insightful discussions on the topic
of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned
in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Vitaliy
full_name: ' Kurlin , Vitaliy'
last_name: ' Kurlin '
- first_name: Philip
full_name: Smith, Philip
last_name: Smith
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. The density fingerprint
of a periodic point set. In: 37th International Symposium on Computational
Geometry (SoCG 2021). Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2021:32:1-32:16. doi:10.4230/LIPIcs.SoCG.2021.32'
apa: 'Edelsbrunner, H., Heiss, T., Kurlin , V., Smith, P., & Wintraecken, M.
(2021). The density fingerprint of a periodic point set. In 37th International
Symposium on Computational Geometry (SoCG 2021) (Vol. 189, p. 32:1-32:16).
Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.32'
chicago: Edelsbrunner, Herbert, 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), 189:32:1-32:16.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.32.
ieee: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, and M. Wintraecken, “The
density fingerprint of a periodic point set,” in 37th International Symposium
on Computational Geometry (SoCG 2021), Virtual, 2021, vol. 189, p. 32:1-32:16.
ista: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. 2021. The density
fingerprint of a periodic point set. 37th International Symposium on Computational
Geometry (SoCG 2021). SoCG: Symposium on Computational Geometry, LIPIcs, vol.
189, 32:1-32:16.'
mla: Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point
Set.” 37th International Symposium on Computational Geometry (SoCG 2021),
vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16,
doi:10.4230/LIPIcs.SoCG.2021.32.
short: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, M. Wintraecken, in:, 37th
International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
date_created: 2021-04-22T08:09:58Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2026-04-07T12:54:09Z
day: '02'
ddc:
- '004'
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.32
ec_funded: 1
file:
- access_level: open_access
checksum: 1787baef1523d6d93753b90d0c109a6d
content_type: application/pdf
creator: mwintrae
date_created: 2021-04-22T08:08:14Z
date_updated: 2021-04-22T08:08:14Z
file_id: '9346'
file_name: df_socg_final_version.pdf
file_size: 3117435
relation: main_file
success: 1
file_date_updated: 2021-04-22T08:08:14Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 32:1-32:16
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Persistent Homology, Algorithms and Stochastic Geometry
- _id: 25C5A090-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00312
name: Synaptic communication in neuronal microcircuits
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry (SoCG 2021)
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '18667'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: The density fingerprint of a periodic point set
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '7952'
abstract:
- lang: eng
text: "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 \U0001D4AF 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 \U0001D4AF. 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. "
alternative_title:
- LIPIcs
article_number: 20:1-20:18
article_processing_charge: No
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations
of isomanifolds. In: 36th International Symposium on Computational Geometry.
Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.20'
apa: 'Boissonnat, J.-D., & Wintraecken, M. (2020). The topological correctness
of PL-approximations of isomanifolds. In 36th International Symposium on Computational
Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.20'
chicago: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL-Approximations of Isomanifolds.” In 36th International Symposium on Computational
Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
https://doi.org/10.4230/LIPIcs.SoCG.2020.20.
ieee: J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations
of isomanifolds,” in 36th International Symposium on Computational Geometry,
Zürich, Switzerland, 2020, vol. 164.
ista: 'Boissonnat J-D, Wintraecken M. 2020. The topological correctness of PL-approximations
of isomanifolds. 36th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 164, 20:1-20:18.'
mla: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness
of PL-Approximations of Isomanifolds.” 36th International Symposium on Computational
Geometry, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.20.
short: J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-09T07:24:11Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-04-22T13:45:17Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2020.20
ec_funded: 1
file:
- access_level: open_access
checksum: 38cbfa4f5d484d267a35d44d210df044
content_type: application/pdf
creator: dernst
date_created: 2020-06-17T10:13:34Z
date_updated: 2020-07-14T12:48:06Z
file_id: '7969'
file_name: 2020_LIPIcsSoCG_Boissonnat.pdf
file_size: 1009739
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-143-6
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '9649'
relation: later_version
status: public
scopus_import: '1'
status: public
title: The topological correctness of PL-approximations of isomanifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '8163'
abstract:
- lang: eng
text: Fejes Tóth [3] studied approximations of smooth surfaces in three-space by
piecewise flat triangular meshes with a given number of vertices on the surface
that are optimal with respect to Hausdorff distance. He proves that this Hausdorff
distance decreases inversely proportional with the number of vertices of the approximating
mesh if the surface is convex. He also claims that this Hausdorff distance is
inversely proportional to the square of the number of vertices for a specific
non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by
two congruent circles. We refute this claim, and show that the asymptotic behavior
of the Hausdorff distance is linear, that is the same as for convex surfaces.
acknowledgement: "The authors are greatly indebted to Dror Atariah, Günther Rote and
John Sullivan for discussion and suggestions. The authors also thank Jean-Daniel
Boissonnat, Ramsay Dyer, David de Laat and Rien van de Weijgaert for discussion.
This work has been supported in part by the European Union’s Seventh Framework Programme
for Research of the\r\nEuropean Commission, under FET-Open grant number 255827 (CGL
Computational Geometry Learning) and ERC Grant Agreement number 339025 GUDHI (Algorithmic
Foundations of Geometry Understanding in Higher Dimensions), the European Union’s
Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie
grant agreement number 754411,and the Austrian Science Fund (FWF): Z00342 N31."
article_processing_charge: No
article_type: original
author:
- first_name: Gert
full_name: Vegter, Gert
last_name: Vegter
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Vegter G, Wintraecken M. Refutation of a claim made by Fejes Tóth on the accuracy
of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 2020;57(2):193-199.
doi:10.1556/012.2020.57.2.1454
apa: Vegter, G., & Wintraecken, M. (2020). Refutation of a claim made by Fejes
Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica.
Akadémiai Kiadó. https://doi.org/10.1556/012.2020.57.2.1454
chicago: Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes
Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum
Hungarica. Akadémiai Kiadó, 2020. https://doi.org/10.1556/012.2020.57.2.1454.
ieee: G. Vegter and M. Wintraecken, “Refutation of a claim made by Fejes Tóth on
the accuracy of surface meshes,” Studia Scientiarum Mathematicarum Hungarica,
vol. 57, no. 2. Akadémiai Kiadó, pp. 193–199, 2020.
ista: Vegter G, Wintraecken M. 2020. Refutation of a claim made by Fejes Tóth on
the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 57(2),
193–199.
mla: Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes
Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum
Hungarica, vol. 57, no. 2, Akadémiai Kiadó, 2020, pp. 193–99, doi:10.1556/012.2020.57.2.1454.
short: G. Vegter, M. Wintraecken, Studia Scientiarum Mathematicarum Hungarica 57
(2020) 193–199.
corr_author: '1'
date_created: 2020-07-24T07:09:18Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2025-04-15T07:16:57Z
day: '24'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1556/012.2020.57.2.1454
ec_funded: 1
external_id:
isi:
- '000570978400005'
file:
- access_level: open_access
content_type: application/pdf
creator: mwintrae
date_created: 2020-07-24T07:09:06Z
date_updated: 2020-07-24T07:09:06Z
file_id: '8164'
file_name: 57-2-05_4214-1454Vegter-Wintraecken_OpenAccess_CC-BY-NC.pdf
file_size: 1476072
relation: main_file
file_date_updated: 2020-07-24T07:09:06Z
has_accepted_license: '1'
intvolume: ' 57'
isi: 1
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 193-199
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: Studia Scientiarum Mathematicarum Hungarica
publication_identifier:
eissn:
- 1588-2896
issn:
- 0081-6906
publication_status: published
publisher: Akadémiai Kiadó
quality_controlled: '1'
scopus_import: '1'
status: public
title: Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2020'
...
---
_id: '7567'
abstract:
- lang: eng
text: Coxeter triangulations are triangulations of Euclidean space based on a single
simplex. By this we mean that given an individual simplex we can recover the entire
triangulation of Euclidean space by inductively reflecting in the faces of the
simplex. In this paper we establish that the quality of the simplices in all Coxeter
triangulations is O(1/d−−√) of the quality of regular simplex. We further investigate
the Delaunay property for these triangulations. Moreover, we consider an extension
of the Delaunay property, namely protection, which is a measure of non-degeneracy
of a Delaunay triangulation. In particular, one family of Coxeter triangulations
achieves the protection O(1/d2). We conjecture that both bounds are optimal for
triangulations in Euclidean space.
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Aruni
full_name: Choudhary, Aruni
last_name: Choudhary
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Choudhary A, Kachanovich S, Wintraecken M. Coxeter triangulations have good
quality. Mathematics in Computer Science. 2020;14:141-176. doi:10.1007/s11786-020-00461-5
apa: Choudhary, A., Kachanovich, S., & Wintraecken, M. (2020). Coxeter triangulations
have good quality. Mathematics in Computer Science. Springer Nature. https://doi.org/10.1007/s11786-020-00461-5
chicago: Choudhary, Aruni, Siargey Kachanovich, and Mathijs Wintraecken. “Coxeter
Triangulations Have Good Quality.” Mathematics in Computer Science. Springer
Nature, 2020. https://doi.org/10.1007/s11786-020-00461-5.
ieee: A. Choudhary, S. Kachanovich, and M. Wintraecken, “Coxeter triangulations
have good quality,” Mathematics in Computer Science, vol. 14. Springer
Nature, pp. 141–176, 2020.
ista: Choudhary A, Kachanovich S, Wintraecken M. 2020. Coxeter triangulations have
good quality. Mathematics in Computer Science. 14, 141–176.
mla: Choudhary, Aruni, et al. “Coxeter Triangulations Have Good Quality.” Mathematics
in Computer Science, vol. 14, Springer Nature, 2020, pp. 141–76, doi:10.1007/s11786-020-00461-5.
short: A. Choudhary, S. Kachanovich, M. Wintraecken, Mathematics in Computer Science
14 (2020) 141–176.
corr_author: '1'
date_created: 2020-03-05T13:30:18Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2025-04-14T07:44:03Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s11786-020-00461-5
ec_funded: 1
file:
- access_level: open_access
checksum: 1d145f3ab50ccee735983cb89236e609
content_type: application/pdf
creator: dernst
date_created: 2020-11-20T10:18:02Z
date_updated: 2020-11-20T10:18:02Z
file_id: '8783'
file_name: 2020_MathCompScie_Choudhary.pdf
file_size: 872275
relation: main_file
success: 1
file_date_updated: 2020-11-20T10:18:02Z
has_accepted_license: '1'
intvolume: ' 14'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 141-176
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Mathematics in Computer Science
publication_identifier:
eissn:
- 1661-8289
issn:
- 1661-8270
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Coxeter triangulations have good quality
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2020'
...