---
_id: '9630'
abstract:
- lang: eng
text: Various kinds of data are routinely represented as discrete probability distributions.
Examples include text documents summarized by histograms of word occurrences and
images represented as histograms of oriented gradients. Viewing a discrete probability
distribution as a point in the standard simplex of the appropriate dimension,
we can understand collections of such objects in geometric and topological terms. Importantly,
instead of using the standard Euclidean distance, we look into dissimilarity measures
with information-theoretic justification, and we develop the theory needed for
applying topological data analysis in this setting. In doing so, we emphasize
constructions that enable the usage of existing computational topology software
in this context.
acknowledgement: This research is partially supported by the Office of Naval Research,
through grant no. N62909-18-1-2038, and 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
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: Ziga
full_name: Virk, Ziga
id: 2E36B656-F248-11E8-B48F-1D18A9856A87
last_name: Virk
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: Edelsbrunner H, Virk Z, Wagner H. Topological data analysis in information
space. Journal of Computational Geometry. 2020;11(2):162-182. doi:10.20382/jocg.v11i2a7
apa: Edelsbrunner, H., Virk, Z., & Wagner, H. (2020). Topological data analysis
in information space. Journal of Computational Geometry. Carleton University.
https://doi.org/10.20382/jocg.v11i2a7
chicago: Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Topological Data
Analysis in Information Space.” Journal of Computational Geometry. Carleton
University, 2020. https://doi.org/10.20382/jocg.v11i2a7.
ieee: H. Edelsbrunner, Z. Virk, and H. Wagner, “Topological data analysis in information
space,” Journal of Computational Geometry, vol. 11, no. 2. Carleton University,
pp. 162–182, 2020.
ista: Edelsbrunner H, Virk Z, Wagner H. 2020. Topological data analysis in information
space. Journal of Computational Geometry. 11(2), 162–182.
mla: Edelsbrunner, Herbert, et al. “Topological Data Analysis in Information Space.”
Journal of Computational Geometry, vol. 11, no. 2, Carleton University,
2020, pp. 162–82, doi:10.20382/jocg.v11i2a7.
short: H. Edelsbrunner, Z. Virk, H. Wagner, Journal of Computational Geometry 11
(2020) 162–182.
date_created: 2021-07-04T22:01:26Z
date_published: 2020-12-14T00:00:00Z
date_updated: 2021-08-11T12:26:34Z
day: '14'
ddc:
- '510'
- '000'
department:
- _id: HeEd
doi: 10.20382/jocg.v11i2a7
file:
- access_level: open_access
checksum: f02d0b2b3838e7891a6c417fc34ffdcd
content_type: application/pdf
creator: asandaue
date_created: 2021-08-11T11:55:11Z
date_updated: 2021-08-11T11:55:11Z
file_id: '9882'
file_name: 2020_JournalOfComputationalGeometry_Edelsbrunner.pdf
file_size: 1449234
relation: main_file
success: 1
file_date_updated: 2021-08-11T11:55:11Z
has_accepted_license: '1'
intvolume: ' 11'
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '12'
oa: 1
oa_version: Published Version
page: 162-182
project:
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Discretization in Geometry and Dynamics
publication: Journal of Computational Geometry
publication_identifier:
eissn:
- 1920180X
publication_status: published
publisher: Carleton University
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topological data analysis in information space
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 11
year: '2020'
...
---
_id: '7950'
abstract:
- lang: eng
text: "The input to the token swapping problem is a graph with vertices v1, v2,
. . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The
goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number
of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token
swapping on a tree, also known as “sorting with a transposition tree,” is not
known to be in P nor NP-complete. We present some partial results:\r\n1. An
optimum swap sequence may need to perform a swap on a leaf vertex that has the
correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2. Any
algorithm that fixes happy leaves—as all known approximation algorithms for the
problem do—has approximation factor at least 4/3. Furthermore, the two best-known
2-approximation algorithms have approximation factor exactly 2.\r\n3. A generalized
problem—weighted coloured token swapping—is NP-complete on trees, but solvable
in polynomial time on paths and stars. In this version, tokens and vertices
\ have colours, and colours have weights. The goal is to get every
token to a vertex of the same colour, and the cost of a swap is the sum of the
weights of the two tokens involved."
article_number: '1903.06981'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ahmad
full_name: Biniaz, Ahmad
last_name: Biniaz
- first_name: Kshitij
full_name: Jain, Kshitij
last_name: Jain
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Tillmann
full_name: Miltzow, Tillmann
last_name: Miltzow
- first_name: Debajyoti
full_name: Mondal, Debajyoti
last_name: Mondal
- first_name: Anurag Murty
full_name: Naredla, Anurag Murty
last_name: Naredla
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Alexi
full_name: Turcotte, Alexi
last_name: Turcotte
citation:
ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (n.d.). Token swapping on trees. arXiv.
chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
Swapping on Trees.” ArXiv, n.d.
ieee: A. Biniaz et al., “Token swapping on trees,” arXiv. .
ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.
mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.
short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
J. Tkadlec, A. Turcotte, ArXiv (n.d.).
date_created: 2020-06-08T12:25:25Z
date_published: 2019-03-16T00:00:00Z
date_updated: 2024-01-04T12:42:08Z
day: '16'
department:
- _id: HeEd
- _id: UlWa
- _id: KrCh
external_id:
arxiv:
- '1903.06981'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.06981
month: '03'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
related_material:
record:
- id: '7944'
relation: dissertation_contains
status: public
- id: '12833'
relation: later_version
status: public
status: public
title: Token swapping on trees
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6628'
abstract:
- lang: eng
text: Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces
in Euclidean space by piecewise flat triangular meshes with a given number
of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this
Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and
d is the dimension of Euclidean space. Moreover the pro-portionality constant
can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In
this short note, we prove the extrinsic nature of this constant for manifolds
of sufficiently high codimension. We do so by constructing an family of isometric
embeddings of the flat torus in Euclidean space.
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. The extrinsic nature of the Hausdorff distance of
optimal triangulations of manifolds. In: The 31st Canadian Conference in Computational
Geometry. ; 2019:275-279.'
apa: Vegter, G., & Wintraecken, M. (2019). The extrinsic nature of the Hausdorff
distance of optimal triangulations of manifolds. In The 31st Canadian Conference
in Computational Geometry (pp. 275–279). Edmonton, Canada.
chicago: Vegter, Gert, and Mathijs Wintraecken. “The Extrinsic Nature of the Hausdorff
Distance of Optimal Triangulations of Manifolds.” In The 31st Canadian Conference
in Computational Geometry, 275–79, 2019.
ieee: G. Vegter and M. Wintraecken, “The extrinsic nature of the Hausdorff distance
of optimal triangulations of manifolds,” in The 31st Canadian Conference in
Computational Geometry, Edmonton, Canada, 2019, pp. 275–279.
ista: 'Vegter G, Wintraecken M. 2019. The extrinsic nature of the Hausdorff distance
of optimal triangulations of manifolds. The 31st Canadian Conference in Computational
Geometry. CCCG: Canadian Conference in Computational Geometry, 275–279.'
mla: Vegter, Gert, and Mathijs Wintraecken. “The Extrinsic Nature of the Hausdorff
Distance of Optimal Triangulations of Manifolds.” The 31st Canadian Conference
in Computational Geometry, 2019, pp. 275–79.
short: G. Vegter, M. Wintraecken, in:, The 31st Canadian Conference in Computational
Geometry, 2019, pp. 275–279.
conference:
end_date: 2019-08-10
location: Edmonton, Canada
name: 'CCCG: Canadian Conference in Computational Geometry'
start_date: 2019-08-08
date_created: 2019-07-12T08:34:57Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2021-01-12T08:08:16Z
day: '01'
ddc:
- '004'
department:
- _id: HeEd
ec_funded: 1
file:
- access_level: open_access
checksum: ceabd152cfa55170d57763f9c6c60a53
content_type: application/pdf
creator: mwintrae
date_created: 2019-07-12T08:32:46Z
date_updated: 2020-07-14T12:47:34Z
file_id: '6629'
file_name: IntrinsicExtrinsicCCCG2019.pdf
file_size: 321176
relation: main_file
file_date_updated: 2020-07-14T12:47:34Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 275-279
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: The 31st Canadian Conference in Computational Geometry
publication_status: published
quality_controlled: '1'
scopus_import: 1
status: public
title: The extrinsic nature of the Hausdorff distance of optimal triangulations of
manifolds
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6634'
abstract:
- lang: eng
text: In this paper we prove several new results around Gromov's waist theorem.
We give a simple proof of Vaaler's theorem on sections of the unit cube using
the Borsuk-Ulam-Crofton technique, consider waists of real and complex projective
spaces, flat tori, convex bodies in Euclidean space; and establish waist-type
results in terms of the Hausdorff measure.
article_processing_charge: No
arxiv: 1
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Alfredo
full_name: Hubard, Alfredo
last_name: Hubard
- first_name: Roman
full_name: Karasev, Roman
last_name: Karasev
citation:
ama: Akopyan A, Hubard A, Karasev R. Lower and upper bounds for the waists of different
spaces. Topological Methods in Nonlinear Analysis. 2019;53(2):457-490.
doi:10.12775/TMNA.2019.008
apa: Akopyan, A., Hubard, A., & Karasev, R. (2019). Lower and upper bounds for
the waists of different spaces. Topological Methods in Nonlinear Analysis.
Akademicka Platforma Czasopism. https://doi.org/10.12775/TMNA.2019.008
chicago: Akopyan, Arseniy, Alfredo Hubard, and Roman Karasev. “Lower and Upper Bounds
for the Waists of Different Spaces.” Topological Methods in Nonlinear Analysis.
Akademicka Platforma Czasopism, 2019. https://doi.org/10.12775/TMNA.2019.008.
ieee: A. Akopyan, A. Hubard, and R. Karasev, “Lower and upper bounds for the waists
of different spaces,” Topological Methods in Nonlinear Analysis, vol. 53,
no. 2. Akademicka Platforma Czasopism, pp. 457–490, 2019.
ista: Akopyan A, Hubard A, Karasev R. 2019. Lower and upper bounds for the waists
of different spaces. Topological Methods in Nonlinear Analysis. 53(2), 457–490.
mla: Akopyan, Arseniy, et al. “Lower and Upper Bounds for the Waists of Different
Spaces.” Topological Methods in Nonlinear Analysis, vol. 53, no. 2, Akademicka
Platforma Czasopism, 2019, pp. 457–90, doi:10.12775/TMNA.2019.008.
short: A. Akopyan, A. Hubard, R. Karasev, Topological Methods in Nonlinear Analysis
53 (2019) 457–490.
date_created: 2019-07-14T21:59:19Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-08-29T06:32:48Z
day: '01'
department:
- _id: HeEd
doi: 10.12775/TMNA.2019.008
ec_funded: 1
external_id:
arxiv:
- '1612.06926'
isi:
- '000472541600004'
intvolume: ' 53'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1612.06926
month: '06'
oa: 1
oa_version: Preprint
page: 457-490
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Topological Methods in Nonlinear Analysis
publication_status: published
publisher: Akademicka Platforma Czasopism
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower and upper bounds for the waists of different spaces
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 53
year: '2019'
...
---
_id: '6648'
abstract:
- lang: eng
text: "Various kinds of data are routinely represented as discrete probability distributions.
Examples include text documents summarized by histograms of word occurrences and
images represented as histograms of oriented gradients. Viewing a discrete probability
distribution as a point in the standard simplex of the appropriate dimension,
we can understand collections of such objects in geometric and topological terms.
Importantly, instead of using the standard Euclidean distance, we look into dissimilarity
measures with information-theoretic justification, and we develop the theory\r\nneeded
for applying topological data analysis in this setting. In doing so, we emphasize
constructions that enable the usage of existing computational topology software
in this context."
alternative_title:
- LIPIcs
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: Ziga
full_name: Virk, Ziga
last_name: Virk
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: 'Edelsbrunner H, Virk Z, Wagner H. Topological data analysis in information
space. In: 35th International Symposium on Computational Geometry. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:31:1-31:14. doi:10.4230/LIPICS.SOCG.2019.31'
apa: 'Edelsbrunner, H., Virk, Z., & Wagner, H. (2019). Topological data analysis
in information space. In 35th International Symposium on Computational Geometry
(Vol. 129, p. 31:1-31:14). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.31'
chicago: Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Topological Data
Analysis in Information Space.” In 35th International Symposium on Computational
Geometry, 129:31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019. https://doi.org/10.4230/LIPICS.SOCG.2019.31.
ieee: H. Edelsbrunner, Z. Virk, and H. Wagner, “Topological data analysis in information
space,” in 35th International Symposium on Computational Geometry, Portland,
OR, United States, 2019, vol. 129, p. 31:1-31:14.
ista: 'Edelsbrunner H, Virk Z, Wagner H. 2019. Topological data analysis in information
space. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129, 31:1-31:14.'
mla: Edelsbrunner, Herbert, et al. “Topological Data Analysis in Information Space.”
35th International Symposium on Computational Geometry, vol. 129, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 31:1-31:14, doi:10.4230/LIPICS.SOCG.2019.31.
short: H. Edelsbrunner, Z. Virk, H. Wagner, in:, 35th International Symposium on
Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019,
p. 31:1-31:14.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-07-17T10:36:09Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:08:23Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPICS.SOCG.2019.31
external_id:
arxiv:
- '1903.08510'
file:
- access_level: open_access
checksum: 8ec8720730d4c789bf7b06540f1c29f4
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:40:01Z
date_updated: 2020-07-14T12:47:35Z
file_id: '6666'
file_name: 2019_LIPICS_Edelsbrunner.pdf
file_size: 1355179
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 31:1-31:14
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Topological data analysis in information 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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6671'
abstract:
- lang: eng
text: 'In this paper we discuss three results. The first two concern general sets
of positive reach: we first characterize the reach of a closed set by means of
a bound on the metric distortion between the distance measured in the ambient
Euclidean space and the shortest path distance measured in the set. Secondly,
we prove that the intersection of a ball with radius less than the reach with
the set is geodesically convex, meaning that the shortest path between any two
points in the intersection lies itself in the intersection. For our third result
we focus on manifolds with positive reach and give a bound on the angle between
tangent spaces at two different points in terms of the reach and the distance
between the two points.'
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: 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: Boissonnat J-D, Lieutier A, Wintraecken M. The reach, metric distortion, geodesic
convexity and the variation of tangent spaces. Journal of Applied and Computational
Topology. 2019;3(1-2):29–58. doi:10.1007/s41468-019-00029-8
apa: Boissonnat, J.-D., Lieutier, A., & Wintraecken, M. (2019). The reach, metric
distortion, geodesic convexity and the variation of tangent spaces. Journal
of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-019-00029-8
chicago: Boissonnat, Jean-Daniel, André Lieutier, and Mathijs Wintraecken. “The
Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.”
Journal of Applied and Computational Topology. Springer Nature, 2019. https://doi.org/10.1007/s41468-019-00029-8.
ieee: J.-D. Boissonnat, A. Lieutier, and M. Wintraecken, “The reach, metric distortion,
geodesic convexity and the variation of tangent spaces,” Journal of Applied
and Computational Topology, vol. 3, no. 1–2. Springer Nature, pp. 29–58, 2019.
ista: Boissonnat J-D, Lieutier A, Wintraecken M. 2019. The reach, metric distortion,
geodesic convexity and the variation of tangent spaces. Journal of Applied and
Computational Topology. 3(1–2), 29–58.
mla: Boissonnat, Jean-Daniel, et al. “The Reach, Metric Distortion, Geodesic Convexity
and the Variation of Tangent Spaces.” Journal of Applied and Computational
Topology, vol. 3, no. 1–2, Springer Nature, 2019, pp. 29–58, doi:10.1007/s41468-019-00029-8.
short: J.-D. Boissonnat, A. Lieutier, M. Wintraecken, Journal of Applied and Computational
Topology 3 (2019) 29–58.
date_created: 2019-07-24T08:37:29Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-08-22T12:37:47Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s41468-019-00029-8
ec_funded: 1
file:
- access_level: open_access
checksum: a5b244db9f751221409cf09c97ee0935
content_type: application/pdf
creator: dernst
date_created: 2019-07-31T08:09:56Z
date_updated: 2020-07-14T12:47:36Z
file_id: '6741'
file_name: 2019_JournAppliedComputTopol_Boissonnat.pdf
file_size: 2215157
relation: main_file
file_date_updated: 2020-07-14T12:47:36Z
has_accepted_license: '1'
intvolume: ' 3'
issue: 1-2
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 29–58
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: The reach, metric distortion, geodesic convexity and the variation of tangent
spaces
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: 3
year: '2019'
...
---
_id: '6756'
abstract:
- lang: eng
text: "We study the topology generated by the temperature fluctuations of the cosmic
microwave background (CMB) radiation, as quantified by the number of components
and holes, formally given by the Betti numbers, in the growing excursion sets.
We compare CMB maps observed by the Planck satellite with a thousand simulated
maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations.
The comparison is multi-scale, being performed on a sequence of degraded maps
with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over
\U0001D54A2 is incomplete due to obfuscation effects by bright point sources and
other extended foreground objects like our own galaxy. To deal with such situations,
where analysis in the presence of “masks” is of importance, we introduce the concept
of relative homology. The parametric χ2-test shows differences between observations
and simulations, yielding p-values at percent to less than permil levels roughly
between 2 and 7°, with the difference in the number of components and holes peaking
at more than 3σ sporadically at these scales. The highest observed deviation between
the observations and simulations for b0 and b1 is approximately between 3σ and
4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler
characteristic at 3.66° in the literature, computed from independent measurements
of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave
Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler
characteristic is phenomenologically related to the strongly anomalous behaviour
of components and holes, or the zeroth and first Betti numbers, respectively.
Further, since these topological descriptors show consistent anomalous behaviour
over independent measurements of Planck and WMAP, instrumental and systematic
errors may be an unlikely source. These are also the scales at which the observed
maps exhibit low variance compared to the simulations, and approximately the range
of scales at which the power spectrum exhibits a dip with respect to the theoretical
model. Non-parametric tests show even stronger differences at almost all scales.
Crucially, Gaussian simulations based on power-spectrum matching the characteristics
of the observed dipped power spectrum are not able to resolve the anomaly. Understanding
the origin of the anomalies in the CMB, whether cosmological in nature or arising
due to late-time effects, is an extremely challenging task. Regardless, beyond
the trivial possibility that this may still be a manifestation of an extreme Gaussian
case, these observations, along with the super-horizon scales involved, may motivate
the study of primordial non-Gaussianity. Alternative scenarios worth exploring
may be models with non-trivial topology, including topological defect models."
article_number: A163
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Pratyush
full_name: Pranav, Pratyush
last_name: Pranav
- first_name: Robert J.
full_name: Adler, Robert J.
last_name: Adler
- first_name: Thomas
full_name: Buchert, Thomas
last_name: Buchert
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Bernard J.T.
full_name: Jones, Bernard J.T.
last_name: Jones
- first_name: Armin
full_name: Schwartzman, Armin
last_name: Schwartzman
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
- first_name: Rien
full_name: Van De Weygaert, Rien
last_name: Van De Weygaert
citation:
ama: Pranav P, Adler RJ, Buchert T, et al. Unexpected topology of the temperature
fluctuations in the cosmic microwave background. Astronomy and Astrophysics.
2019;627. doi:10.1051/0004-6361/201834916
apa: Pranav, P., Adler, R. J., Buchert, T., Edelsbrunner, H., Jones, B. J. T., Schwartzman,
A., … Van De Weygaert, R. (2019). Unexpected topology of the temperature fluctuations
in the cosmic microwave background. Astronomy and Astrophysics. EDP Sciences.
https://doi.org/10.1051/0004-6361/201834916
chicago: Pranav, Pratyush, Robert J. Adler, Thomas Buchert, Herbert Edelsbrunner,
Bernard J.T. Jones, Armin Schwartzman, Hubert Wagner, and Rien Van De Weygaert.
“Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.”
Astronomy and Astrophysics. EDP Sciences, 2019. https://doi.org/10.1051/0004-6361/201834916.
ieee: P. Pranav et al., “Unexpected topology of the temperature fluctuations
in the cosmic microwave background,” Astronomy and Astrophysics, vol. 627.
EDP Sciences, 2019.
ista: Pranav P, Adler RJ, Buchert T, Edelsbrunner H, Jones BJT, Schwartzman A, Wagner
H, Van De Weygaert R. 2019. Unexpected topology of the temperature fluctuations
in the cosmic microwave background. Astronomy and Astrophysics. 627, A163.
mla: Pranav, Pratyush, et al. “Unexpected Topology of the Temperature Fluctuations
in the Cosmic Microwave Background.” Astronomy and Astrophysics, vol. 627,
A163, EDP Sciences, 2019, doi:10.1051/0004-6361/201834916.
short: P. Pranav, R.J. Adler, T. Buchert, H. Edelsbrunner, B.J.T. Jones, A. Schwartzman,
H. Wagner, R. Van De Weygaert, Astronomy and Astrophysics 627 (2019).
date_created: 2019-08-04T21:59:18Z
date_published: 2019-07-17T00:00:00Z
date_updated: 2023-08-29T07:01:48Z
day: '17'
ddc:
- '520'
- '530'
department:
- _id: HeEd
doi: 10.1051/0004-6361/201834916
external_id:
arxiv:
- '1812.07678'
isi:
- '000475839300003'
file:
- access_level: open_access
checksum: 83b9209ed9eefbdcefd89019c5a97805
content_type: application/pdf
creator: dernst
date_created: 2019-08-05T08:08:59Z
date_updated: 2020-07-14T12:47:39Z
file_id: '6766'
file_name: 2019_AstronomyAstrophysics_Pranav.pdf
file_size: 14420451
relation: main_file
file_date_updated: 2020-07-14T12:47:39Z
has_accepted_license: '1'
intvolume: ' 627'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 265683E4-B435-11E9-9278-68D0E5697425
grant_number: M62909-18-1-2038
name: Toward Computational Information Topology
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Astronomy and Astrophysics
publication_identifier:
eissn:
- '14320746'
issn:
- '00046361'
publication_status: published
publisher: EDP Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unexpected topology of the temperature fluctuations in the cosmic microwave
background
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: 627
year: '2019'
...
---
_id: '6793'
abstract:
- lang: eng
text: The Regge symmetry is a set of remarkable relations between two tetrahedra
whose edge lengths are related in a simple fashion. It was first discovered as
a consequence of an asymptotic formula in mathematical physics. Here, we give
a simple geometric proof of Regge symmetries in Euclidean, spherical, and hyperbolic
geometry.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Ivan
full_name: Izmestiev, Ivan
last_name: Izmestiev
citation:
ama: Akopyan A, Izmestiev I. The Regge symmetry, confocal conics, and the Schläfli
formula. Bulletin of the London Mathematical Society. 2019;51(5):765-775.
doi:10.1112/blms.12276
apa: Akopyan, A., & Izmestiev, I. (2019). The Regge symmetry, confocal conics,
and the Schläfli formula. Bulletin of the London Mathematical Society.
London Mathematical Society. https://doi.org/10.1112/blms.12276
chicago: Akopyan, Arseniy, and Ivan Izmestiev. “The Regge Symmetry, Confocal Conics,
and the Schläfli Formula.” Bulletin of the London Mathematical Society.
London Mathematical Society, 2019. https://doi.org/10.1112/blms.12276.
ieee: A. Akopyan and I. Izmestiev, “The Regge symmetry, confocal conics, and the
Schläfli formula,” Bulletin of the London Mathematical Society, vol. 51,
no. 5. London Mathematical Society, pp. 765–775, 2019.
ista: Akopyan A, Izmestiev I. 2019. The Regge symmetry, confocal conics, and the
Schläfli formula. Bulletin of the London Mathematical Society. 51(5), 765–775.
mla: Akopyan, Arseniy, and Ivan Izmestiev. “The Regge Symmetry, Confocal Conics,
and the Schläfli Formula.” Bulletin of the London Mathematical Society,
vol. 51, no. 5, London Mathematical Society, 2019, pp. 765–75, doi:10.1112/blms.12276.
short: A. Akopyan, I. Izmestiev, Bulletin of the London Mathematical Society 51
(2019) 765–775.
date_created: 2019-08-11T21:59:23Z
date_published: 2019-10-01T00:00:00Z
date_updated: 2023-08-29T07:08:34Z
day: '01'
department:
- _id: HeEd
doi: 10.1112/blms.12276
ec_funded: 1
external_id:
arxiv:
- '1903.04929'
isi:
- '000478560200001'
intvolume: ' 51'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.04929
month: '10'
oa: 1
oa_version: Preprint
page: 765-775
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- '14692120'
issn:
- '00246093'
publication_status: published
publisher: London Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Regge symmetry, confocal conics, and the Schläfli formula
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 51
year: '2019'
...
---
_id: '6828'
abstract:
- lang: eng
text: In this paper we construct a family of exact functors from the category of
Whittaker modules of the simple complex Lie algebra of type to the category of
finite-dimensional modules of the graded affine Hecke algebra of type . Using
results of Backelin [2] and of Arakawa-Suzuki [1], we prove that these functors
map standard modules to standard modules (or zero) and simple modules to simple
modules (or zero). Moreover, we show that each simple module of the graded affine
Hecke algebra appears as the image of a simple Whittaker module. Since the Whittaker
category contains the BGG category as a full subcategory, our results generalize
results of Arakawa-Suzuki [1], which in turn generalize Schur-Weyl duality between
finite-dimensional representations of and representations of the symmetric group
.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Adam
full_name: Brown, Adam
id: 70B7FDF6-608D-11E9-9333-8535E6697425
last_name: Brown
citation:
ama: Brown A. Arakawa-Suzuki functors for Whittaker modules. Journal of Algebra.
2019;538:261-289. doi:10.1016/j.jalgebra.2019.07.027
apa: Brown, A. (2019). Arakawa-Suzuki functors for Whittaker modules. Journal
of Algebra. Elsevier. https://doi.org/10.1016/j.jalgebra.2019.07.027
chicago: Brown, Adam. “Arakawa-Suzuki Functors for Whittaker Modules.” Journal
of Algebra. Elsevier, 2019. https://doi.org/10.1016/j.jalgebra.2019.07.027.
ieee: A. Brown, “Arakawa-Suzuki functors for Whittaker modules,” Journal of Algebra,
vol. 538. Elsevier, pp. 261–289, 2019.
ista: Brown A. 2019. Arakawa-Suzuki functors for Whittaker modules. Journal of Algebra.
538, 261–289.
mla: Brown, Adam. “Arakawa-Suzuki Functors for Whittaker Modules.” Journal of
Algebra, vol. 538, Elsevier, 2019, pp. 261–89, doi:10.1016/j.jalgebra.2019.07.027.
short: A. Brown, Journal of Algebra 538 (2019) 261–289.
date_created: 2019-08-22T07:54:13Z
date_published: 2019-11-15T00:00:00Z
date_updated: 2023-08-29T07:11:47Z
day: '15'
department:
- _id: HeEd
doi: 10.1016/j.jalgebra.2019.07.027
external_id:
arxiv:
- '1805.04676'
isi:
- '000487176300011'
intvolume: ' 538'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1805.04676
month: '11'
oa: 1
oa_version: Preprint
page: 261-289
publication: Journal of Algebra
publication_identifier:
issn:
- 0021-8693
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: Arakawa-Suzuki functors for Whittaker modules
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 538
year: '2019'
...
---
_id: '6989'
abstract:
- lang: eng
text: 'When can a polyomino piece of paper be folded into a unit cube? Prior work
studied tree-like polyominoes, but polyominoes with holes remain an intriguing
open problem. We present sufficient conditions for a polyomino with hole(s) to
fold into a cube, and conditions under which cube folding is impossible. In particular,
we show that all but five special simple holes guarantee foldability. '
acknowledgement: This research was performed in part at the 33rd BellairsWinter Workshop on Computational Geometry. Wethank
all other participants for a fruitful atmosphere.
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Hugo A
full_name: Akitaya, Hugo A
last_name: Akitaya
- first_name: Kenneth C
full_name: Cheung, Kenneth C
last_name: Cheung
- first_name: Erik D
full_name: Demaine, Erik D
last_name: Demaine
- first_name: Martin L
full_name: Demaine, Martin L
last_name: Demaine
- first_name: Sandor P
full_name: Fekete, Sandor P
last_name: Fekete
- first_name: Linda
full_name: Kleist, Linda
last_name: Kleist
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Klara
full_name: Mundilova, Klara
last_name: Mundilova
- first_name: Christiane
full_name: Schmidt, Christiane
last_name: Schmidt
citation:
ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
into a cube. In: Proceedings of the 31st Canadian Conference on Computational
Geometry. Canadian Conference on Computational Geometry; 2019:164-170.'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2019). Folding polyominoes with holes into a
cube. In Proceedings of the 31st Canadian Conference on Computational Geometry
(pp. 164–170). Edmonton, Canada: Canadian Conference on Computational Geometry.'
chicago: Aichholzer, Oswin, Hugo A Akitaya, Kenneth C Cheung, Erik D Demaine, Martin
L Demaine, Sandor P Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes
into a Cube.” In Proceedings of the 31st Canadian Conference on Computational
Geometry, 164–70. Canadian Conference on Computational Geometry, 2019.
ieee: O. Aichholzer et al., “Folding polyominoes with holes into a cube,”
in Proceedings of the 31st Canadian Conference on Computational Geometry,
Edmonton, Canada, 2019, pp. 164–170.
ista: 'Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist
L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2019. Folding
polyominoes with holes into a cube. Proceedings of the 31st Canadian Conference
on Computational Geometry. CCCG: Canadian Conference in Computational Geometry,
164–170.'
mla: Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Proceedings
of the 31st Canadian Conference on Computational Geometry, Canadian Conference
on Computational Geometry, 2019, pp. 164–70.
short: O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P.
Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt,
in:, Proceedings of the 31st Canadian Conference on Computational Geometry, Canadian
Conference on Computational Geometry, 2019, pp. 164–170.
conference:
end_date: 2019-08-10
location: Edmonton, Canada
name: 'CCCG: Canadian Conference in Computational Geometry'
start_date: 2019-08-08
date_created: 2019-11-04T16:46:11Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-08-04T10:57:42Z
day: '01'
department:
- _id: HeEd
external_id:
arxiv:
- '1910.09917'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://cccg.ca/proceedings/2019/proceedings.pdf
month: '08'
oa: 1
oa_version: Published Version
page: 164-170
publication: Proceedings of the 31st Canadian Conference on Computational Geometry
publication_status: published
publisher: Canadian Conference on Computational Geometry
quality_controlled: '1'
related_material:
record:
- id: '8317'
relation: extended_version
status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2019'
...
---
_id: '7216'
abstract:
- lang: eng
text: 'We present LiveTraVeL (Live Transit Vehicle Labeling), a real-time system
to label a stream of noisy observations of transit vehicle trajectories with the
transit routes they are serving (e.g., northbound bus #5). In order to scale efficiently
to large transit networks, our system first retrieves a small set of candidate
routes from a geometrically indexed data structure, then applies a fine-grained
scoring step to choose the best match. Given that real-time data remains unavailable
for the majority of the world’s transit agencies, these inferences can help feed
a real-time map of a transit system’s trips, infer transit trip delays in real
time, or measure and correct noisy transit tracking data. This system can run
on vehicle observations from a variety of sources that don’t attach route information
to vehicle observations, such as public imagery streams or user-contributed transit
vehicle sightings.We abstract away the specifics of the sensing system and demonstrate
the effectiveness of our system on a "semisynthetic" dataset of all New York City
buses, where we simulate sensed trajectories by starting with fully labeled vehicle
trajectories reported via the GTFS-Realtime protocol, removing the transit route
IDs, and perturbing locations with synthetic noise. Using just the geometric shapes
of the trajectories, we demonstrate that our system converges on the correct route
ID within a few minutes, even after a vehicle switches from serving one trip to
the next.'
article_number: '8917514'
article_processing_charge: No
author:
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- first_name: James
full_name: Cook, James
last_name: Cook
- first_name: Alex
full_name: Fabrikant, Alex
last_name: Fabrikant
- first_name: Marco
full_name: Gruteser, Marco
last_name: Gruteser
citation:
ama: 'Osang GF, Cook J, Fabrikant A, Gruteser M. LiveTraVeL: Real-time matching
of transit vehicle trajectories to transit routes at scale. In: 2019 IEEE Intelligent
Transportation Systems Conference. IEEE; 2019. doi:10.1109/ITSC.2019.8917514'
apa: 'Osang, G. F., Cook, J., Fabrikant, A., & Gruteser, M. (2019). LiveTraVeL:
Real-time matching of transit vehicle trajectories to transit routes at scale.
In 2019 IEEE Intelligent Transportation Systems Conference. Auckland, New
Zealand: IEEE. https://doi.org/10.1109/ITSC.2019.8917514'
chicago: 'Osang, Georg F, James Cook, Alex Fabrikant, and Marco Gruteser. “LiveTraVeL:
Real-Time Matching of Transit Vehicle Trajectories to Transit Routes at Scale.”
In 2019 IEEE Intelligent Transportation Systems Conference. IEEE, 2019.
https://doi.org/10.1109/ITSC.2019.8917514.'
ieee: 'G. F. Osang, J. Cook, A. Fabrikant, and M. Gruteser, “LiveTraVeL: Real-time
matching of transit vehicle trajectories to transit routes at scale,” in 2019
IEEE Intelligent Transportation Systems Conference, Auckland, New Zealand,
2019.'
ista: 'Osang GF, Cook J, Fabrikant A, Gruteser M. 2019. LiveTraVeL: Real-time matching
of transit vehicle trajectories to transit routes at scale. 2019 IEEE Intelligent
Transportation Systems Conference. ITSC: Intelligent Transportation Systems Conference,
8917514.'
mla: 'Osang, Georg F., et al. “LiveTraVeL: Real-Time Matching of Transit Vehicle
Trajectories to Transit Routes at Scale.” 2019 IEEE Intelligent Transportation
Systems Conference, 8917514, IEEE, 2019, doi:10.1109/ITSC.2019.8917514.'
short: G.F. Osang, J. Cook, A. Fabrikant, M. Gruteser, in:, 2019 IEEE Intelligent
Transportation Systems Conference, IEEE, 2019.
conference:
end_date: 2019-10-30
location: Auckland, New Zealand
name: 'ITSC: Intelligent Transportation Systems Conference'
start_date: 2019-10-27
date_created: 2019-12-29T23:00:47Z
date_published: 2019-11-28T00:00:00Z
date_updated: 2023-09-06T14:50:28Z
day: '28'
department:
- _id: HeEd
doi: 10.1109/ITSC.2019.8917514
external_id:
isi:
- '000521238102050'
isi: 1
language:
- iso: eng
month: '11'
oa_version: None
publication: 2019 IEEE Intelligent Transportation Systems Conference
publication_identifier:
isbn:
- '9781538670248'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'LiveTraVeL: Real-time matching of transit vehicle trajectories to transit
routes at scale'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '5678'
abstract:
- lang: eng
text: "The order-k Voronoi tessellation of a locally finite set \U0001D44B⊆ℝ\U0001D45B
decomposes ℝ\U0001D45B into convex domains whose points have the same k nearest
neighbors in X. Assuming X is a stationary Poisson point process, we give explicit
formulas for the expected number and total area of faces of a given dimension
per unit volume of space. We also develop a relaxed version of discrete Morse
theory and generalize by counting only faces, for which the k nearest points in
X are within a given distance threshold."
article_processing_charge: Yes (via OA deal)
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: 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. Poisson–Delaunay Mosaics of Order k. Discrete
and Computational Geometry. 2019;62(4):865–878. doi:10.1007/s00454-018-0049-2
apa: Edelsbrunner, H., & Nikitenko, A. (2019). Poisson–Delaunay Mosaics of Order
k. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-018-0049-2
chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of
Order K.” Discrete and Computational Geometry. Springer, 2019. https://doi.org/10.1007/s00454-018-0049-2.
ieee: H. Edelsbrunner and A. Nikitenko, “Poisson–Delaunay Mosaics of Order k,” Discrete
and Computational Geometry, vol. 62, no. 4. Springer, pp. 865–878, 2019.
ista: Edelsbrunner H, Nikitenko A. 2019. Poisson–Delaunay Mosaics of Order k. Discrete
and Computational Geometry. 62(4), 865–878.
mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of Order
K.” Discrete and Computational Geometry, vol. 62, no. 4, Springer, 2019,
pp. 865–878, doi:10.1007/s00454-018-0049-2.
short: H. Edelsbrunner, A. Nikitenko, Discrete and Computational Geometry 62 (2019)
865–878.
date_created: 2018-12-16T22:59:20Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2023-09-07T12:07:12Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-018-0049-2
ec_funded: 1
external_id:
arxiv:
- '1709.09380'
isi:
- '000494042900008'
file:
- access_level: open_access
checksum: f9d00e166efaccb5a76bbcbb4dcea3b4
content_type: application/pdf
creator: dernst
date_created: 2019-02-06T10:10:46Z
date_updated: 2020-07-14T12:47:10Z
file_id: '5932'
file_name: 2018_DiscreteCompGeometry_Edelsbrunner.pdf
file_size: 599339
relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
has_accepted_license: '1'
intvolume: ' 62'
isi: 1
issue: '4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 865–878
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
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '6287'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Poisson–Delaunay Mosaics of Order k
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: 62
year: '2019'
...
---
_id: '6050'
abstract:
- lang: eng
text: 'We answer a question of David Hilbert: given two circles it is not possible
in general to construct their centers using only a straightedge. On the other
hand, we give infinitely many families of pairs of circles for which such construction
is possible. '
article_processing_charge: No
arxiv: 1
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: Fedorov, Roman
last_name: Fedorov
citation:
ama: Akopyan A, Fedorov R. Two circles and only a straightedge. Proceedings of
the American Mathematical Society. 2019;147:91-102. doi:10.1090/proc/14240
apa: Akopyan, A., & Fedorov, R. (2019). Two circles and only a straightedge.
Proceedings of the American Mathematical Society. AMS. https://doi.org/10.1090/proc/14240
chicago: Akopyan, Arseniy, and Roman Fedorov. “Two Circles and Only a Straightedge.”
Proceedings of the American Mathematical Society. AMS, 2019. https://doi.org/10.1090/proc/14240.
ieee: A. Akopyan and R. Fedorov, “Two circles and only a straightedge,” Proceedings
of the American Mathematical Society, vol. 147. AMS, pp. 91–102, 2019.
ista: Akopyan A, Fedorov R. 2019. Two circles and only a straightedge. Proceedings
of the American Mathematical Society. 147, 91–102.
mla: Akopyan, Arseniy, and Roman Fedorov. “Two Circles and Only a Straightedge.”
Proceedings of the American Mathematical Society, vol. 147, AMS, 2019,
pp. 91–102, doi:10.1090/proc/14240.
short: A. Akopyan, R. Fedorov, Proceedings of the American Mathematical Society
147 (2019) 91–102.
date_created: 2019-02-24T22:59:19Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2023-08-24T14:48:59Z
day: '01'
department:
- _id: HeEd
doi: 10.1090/proc/14240
external_id:
arxiv:
- '1709.02562'
isi:
- '000450363900008'
intvolume: ' 147'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.02562
month: '01'
oa: 1
oa_version: Preprint
page: 91-102
publication: Proceedings of the American Mathematical Society
publication_status: published
publisher: AMS
quality_controlled: '1'
scopus_import: '1'
status: public
title: Two circles and only a straightedge
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 147
year: '2019'
...
---
_id: '6515'
abstract:
- lang: eng
text: We give non-degeneracy criteria for Riemannian simplices based on simplices
in spaces of constant sectional curvature. It extends previous work on Riemannian
simplices, where we developed Riemannian simplices with respect to Euclidean reference
simplices. The criteria we give in this article are in terms of quality measures
for spaces of constant curvature that we develop here. We see that simplices in
spaces that have nearly constant curvature, are already non-degenerate under very
weak quality demands. This is of importance because it allows for sampling of
Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature.
author:
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- 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: Dyer R, Vegter G, Wintraecken M. Simplices modelled on spaces of constant curvature.
Journal of Computational Geometry . 2019;10(1):223–256. doi:10.20382/jocg.v10i1a9
apa: Dyer, R., Vegter, G., & Wintraecken, M. (2019). Simplices modelled on spaces
of constant curvature. Journal of Computational Geometry . Carleton University.
https://doi.org/10.20382/jocg.v10i1a9
chicago: Dyer, Ramsay, Gert Vegter, and Mathijs Wintraecken. “Simplices Modelled
on Spaces of Constant Curvature.” Journal of Computational Geometry . Carleton
University, 2019. https://doi.org/10.20382/jocg.v10i1a9.
ieee: R. Dyer, G. Vegter, and M. Wintraecken, “Simplices modelled on spaces of constant
curvature,” Journal of Computational Geometry , vol. 10, no. 1. Carleton
University, pp. 223–256, 2019.
ista: Dyer R, Vegter G, Wintraecken M. 2019. Simplices modelled on spaces of constant
curvature. Journal of Computational Geometry . 10(1), 223–256.
mla: Dyer, Ramsay, et al. “Simplices Modelled on Spaces of Constant Curvature.”
Journal of Computational Geometry , vol. 10, no. 1, Carleton University,
2019, pp. 223–256, doi:10.20382/jocg.v10i1a9.
short: R. Dyer, G. Vegter, M. Wintraecken, Journal of Computational Geometry 10
(2019) 223–256.
date_created: 2019-06-03T09:35:33Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2021-01-12T08:07:50Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.20382/jocg.v10i1a9
ec_funded: 1
file:
- access_level: open_access
checksum: 57b4df2f16a74eb499734ec8ee240178
content_type: application/pdf
creator: mwintrae
date_created: 2019-06-03T09:30:01Z
date_updated: 2020-07-14T12:47:32Z
file_id: '6516'
file_name: mainJournalFinal.pdf
file_size: 2170882
relation: main_file
file_date_updated: 2020-07-14T12:47:32Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 223–256
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'Journal of Computational Geometry '
publication_identifier:
issn:
- 1920-180X
publication_status: published
publisher: Carleton University
quality_controlled: '1'
scopus_import: 1
status: public
title: Simplices modelled on spaces of constant curvature
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: 10
year: '2019'
...
---
_id: '6608'
abstract:
- lang: eng
text: We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner
and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete
application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha
complex, and we use the persistence diagram of the distance function to guide
the hole opening and closing operations. The dependences between the holes define
a partial order on the cells in K that characterizes what can and what cannot
be constructed using the operations. The relations in this partial order reveal
structural information about the underlying filtration of complexes beyond what
is expressed by the persistence diagram.
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: 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. Holes and dependences in an ordered complex. Computer
Aided Geometric Design. 2019;73:1-15. doi:10.1016/j.cagd.2019.06.003
apa: Edelsbrunner, H., & Ölsböck, K. (2019). Holes and dependences in an ordered
complex. Computer Aided Geometric Design. Elsevier. https://doi.org/10.1016/j.cagd.2019.06.003
chicago: Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in
an Ordered Complex.” Computer Aided Geometric Design. Elsevier, 2019. https://doi.org/10.1016/j.cagd.2019.06.003.
ieee: H. Edelsbrunner and K. Ölsböck, “Holes and dependences in an ordered complex,”
Computer Aided Geometric Design, vol. 73. Elsevier, pp. 1–15, 2019.
ista: Edelsbrunner H, Ölsböck K. 2019. Holes and dependences in an ordered complex.
Computer Aided Geometric Design. 73, 1–15.
mla: Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an
Ordered Complex.” Computer Aided Geometric Design, vol. 73, Elsevier, 2019,
pp. 1–15, doi:10.1016/j.cagd.2019.06.003.
short: H. Edelsbrunner, K. Ölsböck, Computer Aided Geometric Design 73 (2019) 1–15.
date_created: 2019-07-07T21:59:20Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-09-07T13:15:29Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1016/j.cagd.2019.06.003
ec_funded: 1
external_id:
isi:
- '000485207800001'
file:
- access_level: open_access
checksum: 7c99be505dc7533257d42eb1830cef04
content_type: application/pdf
creator: kschuh
date_created: 2019-07-08T15:24:26Z
date_updated: 2020-07-14T12:47:34Z
file_id: '6624'
file_name: Elsevier_2019_Edelsbrunner.pdf
file_size: 2665013
relation: main_file
file_date_updated: 2020-07-14T12:47:34Z
has_accepted_license: '1'
intvolume: ' 73'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '08'
oa: 1
oa_version: Published Version
page: 1-15
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: Computer Aided Geometric Design
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '7460'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Holes and dependences in an ordered complex
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 73
year: '2019'
...
---
_id: '312'
abstract:
- lang: eng
text: Motivated by biological questions, we study configurations of equal spheres
that neither pack nor cover. Placing their centers on a lattice, we define the
soft density of the configuration by penalizing multiple overlaps. Considering
the 1-parameter family of diagonally distorted 3-dimensional integer lattices,
we show that the soft density is maximized at the FCC lattice.
acknowledgement: This work was partially supported by the DFG Collaborative Research
Center TRR 109, “Discretization in Geometry and Dynamics,” through grant I02979-N35
of the Austrian Science Fund (FWF).
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: Mabel
full_name: Iglesias Ham, Mabel
id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
last_name: Iglesias Ham
citation:
ama: Edelsbrunner H, Iglesias Ham M. On the optimality of the FCC lattice for soft
sphere packing. SIAM J Discrete Math. 2018;32(1):750-782. doi:10.1137/16M1097201
apa: Edelsbrunner, H., & Iglesias Ham, M. (2018). On the optimality of the FCC
lattice for soft sphere packing. SIAM J Discrete Math. Society for Industrial
and Applied Mathematics . https://doi.org/10.1137/16M1097201
chicago: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the
FCC Lattice for Soft Sphere Packing.” SIAM J Discrete Math. Society for
Industrial and Applied Mathematics , 2018. https://doi.org/10.1137/16M1097201.
ieee: H. Edelsbrunner and M. Iglesias Ham, “On the optimality of the FCC lattice
for soft sphere packing,” SIAM J Discrete Math, vol. 32, no. 1. Society
for Industrial and Applied Mathematics , pp. 750–782, 2018.
ista: Edelsbrunner H, Iglesias Ham M. 2018. On the optimality of the FCC lattice
for soft sphere packing. SIAM J Discrete Math. 32(1), 750–782.
mla: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the FCC
Lattice for Soft Sphere Packing.” SIAM J Discrete Math, vol. 32, no. 1,
Society for Industrial and Applied Mathematics , 2018, pp. 750–82, doi:10.1137/16M1097201.
short: H. Edelsbrunner, M. Iglesias Ham, SIAM J Discrete Math 32 (2018) 750–782.
date_created: 2018-12-11T11:45:46Z
date_published: 2018-03-29T00:00:00Z
date_updated: 2023-09-13T09:34:38Z
day: '29'
department:
- _id: HeEd
doi: 10.1137/16M1097201
external_id:
isi:
- '000428958900038'
intvolume: ' 32'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://pdfs.semanticscholar.org/d2d5/6da00fbc674e6a8b1bb9d857167e54200dc6.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 750 - 782
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: SIAM J Discrete Math
publication_identifier:
issn:
- '08954801'
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '7553'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the optimality of the FCC lattice for soft sphere packing
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 32
year: '2018'
...
---
_id: '87'
abstract:
- lang: eng
text: Using the geodesic distance on the n-dimensional sphere, we study the expected
radius function of the Delaunay mosaic of a random set of points. Specifically,
we consider the partition of the mosaic into intervals of the radius function
and determine the expected number of intervals whose radii are less than or equal
to a given threshold. We find that the expectations are essentially the same as
for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the
points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to
the boundary complex of the convex hull in Rn+1, so we also get the expected number
of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in
Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric
to the standard n-simplex equipped with the Fisher information metric. It follows
that the latter space has similar stochastic properties as the n-dimensional Euclidean
space. Our results are therefore relevant in information geometry and in population
genetics.
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: 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. Random inscribed polytopes have similar radius
functions as Poisson-Delaunay mosaics. Annals of Applied Probability. 2018;28(5):3215-3238.
doi:10.1214/18-AAP1389
apa: Edelsbrunner, H., & Nikitenko, A. (2018). Random inscribed polytopes have
similar radius functions as Poisson-Delaunay mosaics. Annals of Applied Probability.
Institute of Mathematical Statistics. https://doi.org/10.1214/18-AAP1389
chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Random Inscribed Polytopes
Have Similar Radius Functions as Poisson-Delaunay Mosaics.” Annals of Applied
Probability. Institute of Mathematical Statistics, 2018. https://doi.org/10.1214/18-AAP1389.
ieee: H. Edelsbrunner and A. Nikitenko, “Random inscribed polytopes have similar
radius functions as Poisson-Delaunay mosaics,” Annals of Applied Probability,
vol. 28, no. 5. Institute of Mathematical Statistics, pp. 3215–3238, 2018.
ista: Edelsbrunner H, Nikitenko A. 2018. Random inscribed polytopes have similar
radius functions as Poisson-Delaunay mosaics. Annals of Applied Probability. 28(5),
3215–3238.
mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Random Inscribed Polytopes Have
Similar Radius Functions as Poisson-Delaunay Mosaics.” Annals of Applied Probability,
vol. 28, no. 5, Institute of Mathematical Statistics, 2018, pp. 3215–38, doi:10.1214/18-AAP1389.
short: H. Edelsbrunner, A. Nikitenko, Annals of Applied Probability 28 (2018) 3215–3238.
date_created: 2018-12-11T11:44:33Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2023-09-15T12:10:35Z
day: '01'
department:
- _id: HeEd
doi: 10.1214/18-AAP1389
external_id:
arxiv:
- '1705.02870'
isi:
- '000442893500018'
intvolume: ' 28'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.02870
month: '10'
oa: 1
oa_version: Preprint
page: 3215 - 3238
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Annals of Applied Probability
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '7967'
quality_controlled: '1'
related_material:
record:
- id: '6287'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Random inscribed polytopes have similar radius functions as Poisson-Delaunay
mosaics
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 28
year: '2018'
...
---
_id: '187'
abstract:
- lang: eng
text: 'Given a locally finite X ⊆ ℝd and a radius r ≥ 0, the k-fold cover of X and
r consists of all points in ℝd that have k or more points of X within distance
r. We consider two filtrations - one in scale obtained by fixing k and increasing
r, and the other in depth obtained by fixing r and decreasing k - and we compute
the persistence diagrams of both. While standard methods suffice for the filtration
in scale, we need novel geometric and topological concepts for the filtration
in depth. In particular, we introduce a rhomboid tiling in ℝd+1 whose horizontal
integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module
from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers. '
acknowledgement: This work is 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).
alternative_title:
- LIPIcs
article_number: '34'
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
citation:
ama: 'Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls.
In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.34'
apa: 'Edelsbrunner, H., & Osang, G. F. (2018). The multi-cover persistence of
Euclidean balls (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.34'
chicago: Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence
of Euclidean Balls,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.34.
ieee: 'H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean
balls,” presented at the SoCG: Symposium on Computational Geometry, Budapest,
Hungary, 2018, vol. 99.'
ista: 'Edelsbrunner H, Osang GF. 2018. The multi-cover persistence of Euclidean
balls. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 34.'
mla: Edelsbrunner, Herbert, and Georg F. Osang. The Multi-Cover Persistence of
Euclidean Balls. Vol. 99, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018, doi:10.4230/LIPIcs.SoCG.2018.34.
short: H. Edelsbrunner, G.F. Osang, in:, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2018.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:05Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2023-09-07T13:29:00Z
day: '11'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2018.34
file:
- access_level: open_access
checksum: d8c0533ad0018eb4ed1077475eb8fc18
content_type: application/pdf
creator: dernst
date_created: 2018-12-18T09:27:22Z
date_updated: 2020-07-14T12:45:19Z
file_id: '5738'
file_name: 2018_LIPIcs_Edelsbrunner_Osang.pdf
file_size: 528018
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7732'
quality_controlled: '1'
related_material:
record:
- id: '9317'
relation: later_version
status: public
- id: '9056'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: The multi-cover persistence of Euclidean balls
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: 99
year: '2018'
...
---
_id: '188'
abstract:
- lang: eng
text: Smallest enclosing spheres of finite point sets are central to methods in
topological data analysis. Focusing on Bregman divergences to measure dissimilarity,
we prove bounds on the location of the center of a smallest enclosing sphere.
These bounds depend on the range of radii for which Bregman balls are convex.
acknowledgement: This research is partially supported by the Office of Naval Research,
through grant no. N62909-18-1-2038, and the DFG Collaborative Research Center TRR
109, ‘Discretization in Geometry and Dynamics’, through grant no. I02979-N35 of
the Austrian Science Fund
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Ziga
full_name: Virk, Ziga
last_name: Virk
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: 'Edelsbrunner H, Virk Z, Wagner H. Smallest enclosing spheres and Chernoff
points in Bregman geometry. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2018:35:1-35:13. doi:10.4230/LIPIcs.SoCG.2018.35'
apa: 'Edelsbrunner, H., Virk, Z., & Wagner, H. (2018). Smallest enclosing spheres
and Chernoff points in Bregman geometry (Vol. 99, p. 35:1-35:13). Presented at
the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.35'
chicago: Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Smallest Enclosing
Spheres and Chernoff Points in Bregman Geometry,” 99:35:1-35:13. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.35.
ieee: 'H. Edelsbrunner, Z. Virk, and H. Wagner, “Smallest enclosing spheres and
Chernoff points in Bregman geometry,” presented at the SoCG: Symposium on Computational
Geometry, Budapest, Hungary, 2018, vol. 99, p. 35:1-35:13.'
ista: 'Edelsbrunner H, Virk Z, Wagner H. 2018. Smallest enclosing spheres and Chernoff
points in Bregman geometry. SoCG: Symposium on Computational Geometry, Leibniz
International Proceedings in Information, LIPIcs, vol. 99, 35:1-35:13.'
mla: Edelsbrunner, Herbert, et al. Smallest Enclosing Spheres and Chernoff Points
in Bregman Geometry. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018, p. 35:1-35:13, doi:10.4230/LIPIcs.SoCG.2018.35.
short: H. Edelsbrunner, Z. Virk, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2018, p. 35:1-35:13.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:05Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2021-01-12T06:53:48Z
day: '11'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2018.35
file:
- access_level: open_access
checksum: 7509403803b3ac1aee94bbc2ad293d21
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T16:31:31Z
date_updated: 2020-07-14T12:45:20Z
file_id: '5724'
file_name: 2018_LIPIcs_Edelsbrunner.pdf
file_size: 489080
relation: main_file
file_date_updated: 2020-07-14T12:45:20Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 35:1 - 35:13
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7733'
quality_controlled: '1'
scopus_import: 1
status: public
title: Smallest enclosing spheres and Chernoff points in Bregman geometry
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: 99
year: '2018'
...
---
_id: '193'
abstract:
- lang: eng
text: 'We show attacks on five data-independent memory-hard functions (iMHF) that
were submitted to the password hashing competition (PHC). Informally, an MHF is
a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly
lower hardware and/or energy cost than evaluating a single instance on a standard
single-core architecture. Data-independent means the memory access pattern of
the function is independent of the input; this makes iMHFs harder to construct
than data-dependent ones, but the latter can be attacked by various side-channel
attacks. Following [Alwen-Blocki''16], we capture the evaluation of an iMHF as
a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of
this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC.
Ideally, one would like the complexity of a DAG underlying an iMHF to be as close
to quadratic in the number of nodes of the graph as possible. Instead, we show
that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,
TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show
that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have
exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial
property of each underlying DAG (called its depth-robustness. By establishing
upper bounds on this property we are then able to apply the general technique
of [Alwen-Block''16] for analyzing the hardware costs of an iMHF.'
acknowledgement: Leonid Reyzin was supported in part by IST Austria and by US NSF
grants 1012910, 1012798, and 1422965; this research was performed while he was visiting
IST Austria.
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Peter
full_name: Gazi, Peter
last_name: Gazi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Lenoid
full_name: Reyzin, Lenoid
last_name: Reyzin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data
independent password hashing functions. In: Proceedings of the 2018 on Asia
Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534'
apa: 'Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak,
K. Z., … Rybar, M. (2018). On the memory hardness of data independent password
hashing functions. In Proceedings of the 2018 on Asia Conference on Computer
and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534'
chicago: Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F
Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar.
“On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings
of the 2018 on Asia Conference on Computer and Communication Security, 51–65.
ACM, 2018. https://doi.org/10.1145/3196494.3196534.
ieee: J. F. Alwen et al., “On the memory hardness of data independent password
hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.
ista: 'Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin
L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password
hashing functions. Proceedings of the 2018 on Asia Conference on Computer and
Communication Security. ASIACCS: Asia Conference on Computer and Communications
Security , 51–65.'
mla: Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password
Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.
short: J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak,
L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference
on Computer and Communication Security, ACM, 2018, pp. 51–65.
conference:
end_date: 2018-06-08
location: Incheon, Republic of Korea
name: 'ASIACCS: Asia Conference on Computer and Communications Security '
start_date: 2018-06-04
date_created: 2018-12-11T11:45:07Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2023-09-13T09:13:12Z
day: '01'
department:
- _id: KrPi
- _id: HeEd
- _id: VlKo
doi: 10.1145/3196494.3196534
ec_funded: 1
external_id:
isi:
- '000516620100005'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/783
month: '06'
oa: 1
oa_version: Submitted Version
page: 51 - 65
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2018 on Asia Conference on Computer and Communication
Security
publication_status: published
publisher: ACM
publist_id: '7723'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the memory hardness of data independent password hashing functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...