---
_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
date_created: 2020-06-09T07:24:11Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-02T06:49:16Z
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: '74'
abstract:
- lang: eng
text: "We study the Gromov waist in the sense of t-neighborhoods for measures in
the Euclidean space, motivated by the famous theorem of Gromov about
\ the waist of radially symmetric Gaussian measures. In particular, it turns
our possible to extend Gromov’s original result to the case of not necessarily
\ radially symmetric Gaussian measure. We also provide examples of measures
having no t-neighborhood waist property, including a rather wide class\r\nof compactly
supported radially symmetric measures and their maps into the Euclidean space
of dimension at least 2.\r\nWe use a simpler form of Gromov’s pancake argument
\ to produce some estimates of t-neighborhoods of (weighted) volume-critical
submanifolds in the spirit of the waist theorems, including neighborhoods of algebraic
manifolds in the complex projective space. In the appendix of this paper we provide
for reader’s convenience a more detailed explanation of the Caffarelli theorem
that we use to handle not necessarily radially symmetric Gaussian\r\nmeasures."
article_processing_charge: No
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Roman
full_name: Karasev, Roman
last_name: Karasev
citation:
ama: 'Akopyan A, Karasev R. Gromov’s waist of non-radial Gaussian measures and radial
non-Gaussian measures. In: Klartag B, Milman E, eds. Geometric Aspects of Functional
Analysis. Vol 2256. LNM. Springer Nature; 2020:1-27. doi:10.1007/978-3-030-36020-7_1'
apa: Akopyan, A., & Karasev, R. (2020). Gromov’s waist of non-radial Gaussian
measures and radial non-Gaussian measures. In B. Klartag & E. Milman (Eds.),
Geometric Aspects of Functional Analysis (Vol. 2256, pp. 1–27). Springer
Nature. https://doi.org/10.1007/978-3-030-36020-7_1
chicago: Akopyan, Arseniy, and Roman Karasev. “Gromov’s Waist of Non-Radial Gaussian
Measures and Radial Non-Gaussian Measures.” In Geometric Aspects of Functional
Analysis, edited by Bo’az Klartag and Emanuel Milman, 2256:1–27. LNM. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-36020-7_1.
ieee: A. Akopyan and R. Karasev, “Gromov’s waist of non-radial Gaussian measures
and radial non-Gaussian measures,” in Geometric Aspects of Functional Analysis,
vol. 2256, B. Klartag and E. Milman, Eds. Springer Nature, 2020, pp. 1–27.
ista: 'Akopyan A, Karasev R. 2020.Gromov’s waist of non-radial Gaussian measures
and radial non-Gaussian measures. In: Geometric Aspects of Functional Analysis.
vol. 2256, 1–27.'
mla: Akopyan, Arseniy, and Roman Karasev. “Gromov’s Waist of Non-Radial Gaussian
Measures and Radial Non-Gaussian Measures.” Geometric Aspects of Functional
Analysis, edited by Bo’az Klartag and Emanuel Milman, vol. 2256, Springer
Nature, 2020, pp. 1–27, doi:10.1007/978-3-030-36020-7_1.
short: A. Akopyan, R. Karasev, in:, B. Klartag, E. Milman (Eds.), Geometric Aspects
of Functional Analysis, Springer Nature, 2020, pp. 1–27.
date_created: 2018-12-11T11:44:29Z
date_published: 2020-06-21T00:00:00Z
date_updated: 2023-08-17T13:48:31Z
day: '21'
department:
- _id: HeEd
- _id: JaMa
doi: 10.1007/978-3-030-36020-7_1
ec_funded: 1
editor:
- first_name: Bo'az
full_name: Klartag, Bo'az
last_name: Klartag
- first_name: Emanuel
full_name: Milman, Emanuel
last_name: Milman
external_id:
arxiv:
- '1808.07350'
isi:
- '000557689300003'
intvolume: ' 2256'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.07350
month: '06'
oa: 1
oa_version: Preprint
page: 1-27
project:
- _id: 256E75B8-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '716117'
name: Optimal Transport and Stochastic Dynamics
publication: Geometric Aspects of Functional Analysis
publication_identifier:
eisbn:
- '9783030360207'
eissn:
- '16179692'
isbn:
- '9783030360191'
issn:
- '00758434'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNM
status: public
title: Gromov's waist of non-radial Gaussian measures and radial non-Gaussian measures
type: book_chapter
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2256
year: '2020'
...
---
_id: '7554'
abstract:
- lang: eng
text: Slicing a Voronoi tessellation in ${R}^n$ with a $k$-plane gives a $k$-dimensional
weighted Voronoi tessellation, also known as a power diagram or Laguerre tessellation.
Mapping every simplex of the dual weighted Delaunay mosaic to the radius of the
smallest empty circumscribed sphere whose center lies in the $k$-plane gives a
generalized discrete Morse function. Assuming the Voronoi tessellation is generated
by a Poisson point process in ${R}^n$, we study the expected number of simplices
in the $k$-dimensional weighted Delaunay mosaic as well as the expected number
of intervals of the Morse function, both as functions of a radius threshold. As
a by-product, we obtain a new proof for the expected number of connected components
(clumps) in a line section of a circular Boolean model in ${R}^n$.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
citation:
ama: Edelsbrunner H, Nikitenko A. Weighted Poisson–Delaunay mosaics. Theory of
Probability and its Applications. 2020;64(4):595-614. doi:10.1137/S0040585X97T989726
apa: Edelsbrunner, H., & Nikitenko, A. (2020). Weighted Poisson–Delaunay mosaics.
Theory of Probability and Its Applications. SIAM. https://doi.org/10.1137/S0040585X97T989726
chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Weighted Poisson–Delaunay
Mosaics.” Theory of Probability and Its Applications. SIAM, 2020. https://doi.org/10.1137/S0040585X97T989726.
ieee: H. Edelsbrunner and A. Nikitenko, “Weighted Poisson–Delaunay mosaics,” Theory
of Probability and its Applications, vol. 64, no. 4. SIAM, pp. 595–614, 2020.
ista: Edelsbrunner H, Nikitenko A. 2020. Weighted Poisson–Delaunay mosaics. Theory
of Probability and its Applications. 64(4), 595–614.
mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Weighted Poisson–Delaunay Mosaics.”
Theory of Probability and Its Applications, vol. 64, no. 4, SIAM, 2020,
pp. 595–614, doi:10.1137/S0040585X97T989726.
short: H. Edelsbrunner, A. Nikitenko, Theory of Probability and Its Applications
64 (2020) 595–614.
date_created: 2020-03-01T23:00:39Z
date_published: 2020-02-13T00:00:00Z
date_updated: 2023-08-18T06:45:48Z
day: '13'
department:
- _id: HeEd
doi: 10.1137/S0040585X97T989726
ec_funded: 1
external_id:
arxiv:
- '1705.08735'
isi:
- '000551393100007'
intvolume: ' 64'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.08735
month: '02'
oa: 1
oa_version: Preprint
page: 595-614
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Theory of Probability and its Applications
publication_identifier:
eissn:
- '10957219'
issn:
- 0040585X
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Weighted Poisson–Delaunay mosaics
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '7666'
abstract:
- lang: eng
text: Generalizing the decomposition of a connected planar graph into a tree and
a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition
of a smooth vector field. Specifically, we show that for every polyhedral complex,
K, and every dimension, p, there is a partition of the set of p-cells into a maximal
p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the
p-th reduced Betti number of K. Given an ordering of the p-cells, this tri-partition
is unique, and it can be computed by a matrix reduction algorithm that also constructs
canonical bases of cycle and boundary groups.
acknowledgement: This project has received funding from the European Research Council
under the European Union’s Horizon 2020 research and innovation programme (Grant
Agreement No. 78818 Alpha). It is also partially supported by the DFG Collaborative
Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant
No. I02979-N35 of the Austrian Science Fund (FWF).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Katharina
full_name: Ölsböck, Katharina
id: 4D4AA390-F248-11E8-B48F-1D18A9856A87
last_name: Ölsböck
orcid: 0000-0002-4672-8297
citation:
ama: Edelsbrunner H, Ölsböck K. Tri-partitions and bases of an ordered complex.
Discrete and Computational Geometry. 2020;64:759-775. doi:10.1007/s00454-020-00188-x
apa: Edelsbrunner, H., & Ölsböck, K. (2020). Tri-partitions and bases of an
ordered complex. Discrete and Computational Geometry. Springer Nature.
https://doi.org/10.1007/s00454-020-00188-x
chicago: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases
of an Ordered Complex.” Discrete and Computational Geometry. Springer Nature,
2020. https://doi.org/10.1007/s00454-020-00188-x.
ieee: H. Edelsbrunner and K. Ölsböck, “Tri-partitions and bases of an ordered complex,”
Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 759–775,
2020.
ista: Edelsbrunner H, Ölsböck K. 2020. Tri-partitions and bases of an ordered complex.
Discrete and Computational Geometry. 64, 759–775.
mla: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases of
an Ordered Complex.” Discrete and Computational Geometry, vol. 64, Springer
Nature, 2020, pp. 759–75, doi:10.1007/s00454-020-00188-x.
short: H. Edelsbrunner, K. Ölsböck, Discrete and Computational Geometry 64 (2020)
759–775.
date_created: 2020-04-19T22:00:56Z
date_published: 2020-03-20T00:00:00Z
date_updated: 2023-08-21T06:13:48Z
day: '20'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00188-x
ec_funded: 1
external_id:
isi:
- '000520918800001'
file:
- access_level: open_access
checksum: f8cc96e497f00c38340b5dafe0cb91d7
content_type: application/pdf
creator: dernst
date_created: 2020-11-20T13:22:21Z
date_updated: 2020-11-20T13:22:21Z
file_id: '8786'
file_name: 2020_DiscreteCompGeo_Edelsbrunner.pdf
file_size: 701673
relation: main_file
success: 1
file_date_updated: 2020-11-20T13:22:21Z
has_accepted_license: '1'
intvolume: ' 64'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 759-775
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tri-partitions and bases of an ordered complex
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: 64
year: '2020'
...
---
_id: '7962'
abstract:
- lang: eng
text: 'A string graph is the intersection graph of a family of continuous arcs in
the plane. The intersection graph of a family of plane convex sets is a string
graph, but not all string graphs can be obtained in this way. We prove the following
structure theorem conjectured by Janson and Uzzell: The vertex set of almost all
string graphs on n vertices can be partitioned into five cliques such that some
pair of them is not connected by any edge (n→∞). We also show that every graph
with the above property is an intersection graph of plane convex sets. As a corollary,
we obtain that almost all string graphs on n vertices are intersection graphs
of plane convex sets.'
article_processing_charge: No
article_type: original
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Bruce
full_name: Reed, Bruce
last_name: Reed
- first_name: Yelena
full_name: Yuditsky, Yelena
last_name: Yuditsky
citation:
ama: Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs
of plane convex sets. Discrete and Computational Geometry. 2020;63(4):888-917.
doi:10.1007/s00454-020-00213-z
apa: Pach, J., Reed, B., & Yuditsky, Y. (2020). Almost all string graphs are
intersection graphs of plane convex sets. Discrete and Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-020-00213-z
chicago: Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs
Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry.
Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00213-z.
ieee: J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection
graphs of plane convex sets,” Discrete and Computational Geometry, vol.
63, no. 4. Springer Nature, pp. 888–917, 2020.
ista: Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection
graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917.
mla: Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane
Convex Sets.” Discrete and Computational Geometry, vol. 63, no. 4, Springer
Nature, 2020, pp. 888–917, doi:10.1007/s00454-020-00213-z.
short: J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020)
888–917.
date_created: 2020-06-14T22:00:51Z
date_published: 2020-06-05T00:00:00Z
date_updated: 2023-08-21T08:49:18Z
day: '05'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00213-z
external_id:
arxiv:
- '1803.06710'
isi:
- '000538229000001'
intvolume: ' 63'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.06710
month: '06'
oa: 1
oa_version: Preprint
page: 888-917
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Almost all string graphs are intersection graphs of plane convex sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 63
year: '2020'
...