---
_id: '12086'
abstract:
- lang: eng
text: We present a simple algorithm for computing higher-order Delaunay mosaics
that works in Euclidean spaces of any finite dimensions. The algorithm selects
the vertices of the order-k mosaic from incrementally constructed lower-order
mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box
to construct the order-k mosaic from its vertices. Beyond this black-box, the
algorithm uses only combinatorial operations, thus facilitating easy implementation.
We extend this algorithm to compute higher-order α-shapes and provide open-source
implementations. We present experimental results for properties of higher-order
Delaunay mosaics of random point sets.
acknowledgement: Open access funding provided by Austrian Science Fund (FWF). This
project has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme, Grant No. 788183,
from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and
from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry
and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.
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: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
citation:
ama: Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics
and alpha shapes. Algorithmica. 2023;85:277-295. doi:10.1007/s00453-022-01027-6
apa: Edelsbrunner, H., & Osang, G. F. (2023). A simple algorithm for higher-order
Delaunay mosaics and alpha shapes. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-022-01027-6
chicago: Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order
Delaunay Mosaics and Alpha Shapes.” Algorithmica. Springer Nature, 2023.
https://doi.org/10.1007/s00453-022-01027-6.
ieee: H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay
mosaics and alpha shapes,” Algorithmica, vol. 85. Springer Nature, pp.
277–295, 2023.
ista: Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay
mosaics and alpha shapes. Algorithmica. 85, 277–295.
mla: Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order
Delaunay Mosaics and Alpha Shapes.” Algorithmica, vol. 85, Springer Nature,
2023, pp. 277–95, doi:10.1007/s00453-022-01027-6.
short: H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.
date_created: 2022-09-11T22:01:57Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-06-27T12:53:43Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00453-022-01027-6
ec_funded: 1
external_id:
isi:
- '000846967100001'
file:
- access_level: open_access
checksum: 71685ca5121f4c837f40c3f8eb50c915
content_type: application/pdf
creator: dernst
date_created: 2023-01-20T10:02:48Z
date_updated: 2023-01-20T10:02:48Z
file_id: '12322'
file_name: 2023_Algorithmica_Edelsbrunner.pdf
file_size: 911017
relation: main_file
success: 1
file_date_updated: 2023-01-20T10:02:48Z
has_accepted_license: '1'
intvolume: ' 85'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 277-295
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A simple algorithm for higher-order Delaunay mosaics and alpha shapes
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: 2EBD1598-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2023'
...
---
_id: '12709'
abstract:
- lang: eng
text: Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within
distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter
family of spaces that grow larger when r increases or k decreases, called the
multicover bifiltration. Motivated by the problem of computing the homology of
this bifiltration, we introduce two closely related combinatorial bifiltrations,
one polyhedral and the other simplicial, which are both topologically equivalent
to the multicover bifiltration and far smaller than a Čech-based model considered
in prior work of Sheehy. Our polyhedral construction is a bifiltration of the
rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using
a variant of an algorithm given by these authors as well. Using an implementation
for dimension 2 and 3, we provide experimental results. Our simplicial construction
is useful for understanding the polyhedral construction and proving its correctness.
acknowledgement: We thank the anonymous reviewers for many helpful comments and suggestions,
which led to substantial improvements of the paper. The first two authors were supported
by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first
author was partly supported by an Austrian Marshall Plan Scholarship, and by the
Brummer & Partners MathDataLab. A conference version of this paper was presented
at the 37th International Symposium on Computational Geometry (SoCG 2021). Open
access funding provided by the Royal Institute of Technology.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: René
full_name: Corbet, René
last_name: Corbet
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Lesnick, Michael
last_name: Lesnick
- 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: Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration.
Discrete and Computational Geometry. 2023;70:376-405. doi:10.1007/s00454-022-00476-8
apa: Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2023). Computing the
multicover bifiltration. Discrete and Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-022-00476-8
chicago: Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing
the Multicover Bifiltration.” Discrete and Computational Geometry. Springer
Nature, 2023. https://doi.org/10.1007/s00454-022-00476-8.
ieee: R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover
bifiltration,” Discrete and Computational Geometry, vol. 70. Springer Nature,
pp. 376–405, 2023.
ista: Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration.
Discrete and Computational Geometry. 70, 376–405.
mla: Corbet, René, et al. “Computing the Multicover Bifiltration.” Discrete and
Computational Geometry, vol. 70, Springer Nature, 2023, pp. 376–405, doi:10.1007/s00454-022-00476-8.
short: R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational
Geometry 70 (2023) 376–405.
date_created: 2023-03-05T23:01:06Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-10-04T12:03:40Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-022-00476-8
external_id:
arxiv:
- '2103.07823'
isi:
- '000936496800001'
file:
- access_level: open_access
checksum: 71ce7e59f7ee4620acc704fecca620c2
content_type: application/pdf
creator: cchlebak
date_created: 2023-03-07T14:40:14Z
date_updated: 2023-03-07T14:40:14Z
file_id: '12715'
file_name: 2023_DisCompGeo_Corbet.pdf
file_size: 1359323
relation: main_file
success: 1
file_date_updated: 2023-03-07T14:40:14Z
has_accepted_license: '1'
intvolume: ' 70'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 376-405
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '9605'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Computing the multicover bifiltration
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: 70
year: '2023'
...
---
_id: '9056'
abstract:
- lang: eng
text: "In this thesis we study persistence of multi-covers of Euclidean balls and
the geometric structures underlying their computation, in particular Delaunay
mosaics and Voronoi tessellations. The k-fold cover for some discrete input point
set consists of the space where at least k balls of radius r around the input
points overlap. Persistence is a notion that captures, in some sense, the topology
of the shape underlying the input. While persistence is usually computed for the
union of balls, the k-fold cover is of interest as it captures local density,\r\nand
thus might approximate the shape of the input better if the input data is noisy.
To compute persistence of these k-fold covers, we need a discretization that is
provided by higher-order Delaunay mosaics. We present and implement a simple and
efficient algorithm for the computation of higher-order Delaunay mosaics, and
use it to give experimental results for their combinatorial properties. The algorithm
makes use of a new geometric structure, the rhomboid tiling. It contains the higher-order
Delaunay mosaics as slices, and by introducing a filtration\r\nfunction on the
tiling, we also obtain higher-order α-shapes as slices. These allow us to compute
persistence of the multi-covers for varying radius r; the computation for varying
k is less straight-foward and involves the rhomboid tiling directly. We apply
our algorithms to experimental sphere packings to shed light on their structural
properties. Finally, inspired by periodic structures in packings and materials,
we propose and implement an algorithm for periodic Delaunay triangulations to
be integrated into the Computational Geometry Algorithms Library (CGAL), and discuss
the implications on persistence for periodic data sets."
alternative_title:
- ISTA Thesis
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
citation:
ama: Osang GF. Multi-cover persistence and Delaunay mosaics. 2021. doi:10.15479/AT:ISTA:9056
apa: Osang, G. F. (2021). Multi-cover persistence and Delaunay mosaics. Institute
of Science and Technology Austria, Klosterneuburg. https://doi.org/10.15479/AT:ISTA:9056
chicago: Osang, Georg F. “Multi-Cover Persistence and Delaunay Mosaics.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/AT:ISTA:9056.
ieee: G. F. Osang, “Multi-cover persistence and Delaunay mosaics,” Institute of
Science and Technology Austria, Klosterneuburg, 2021.
ista: 'Osang GF. 2021. Multi-cover persistence and Delaunay mosaics. Klosterneuburg:
Institute of Science and Technology Austria.'
mla: Osang, Georg F. Multi-Cover Persistence and Delaunay Mosaics. Institute
of Science and Technology Austria, 2021, doi:10.15479/AT:ISTA:9056.
short: G.F. Osang, Multi-Cover Persistence and Delaunay Mosaics, Institute of Science
and Technology Austria, 2021.
date_created: 2021-02-02T14:11:06Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2023-09-07T13:29:01Z
day: '01'
ddc:
- '006'
- '514'
- '516'
degree_awarded: PhD
department:
- _id: HeEd
- _id: GradSch
doi: 10.15479/AT:ISTA:9056
file:
- access_level: closed
checksum: bcf27986147cab0533b6abadd74e7629
content_type: application/zip
creator: patrickd
date_created: 2021-02-02T14:09:25Z
date_updated: 2021-02-03T10:37:28Z
file_id: '9063'
file_name: thesis_source.zip
file_size: 13446994
relation: source_file
- access_level: open_access
checksum: 9cc8af266579a464385bbe2aff6af606
content_type: application/pdf
creator: patrickd
date_created: 2021-02-02T14:09:18Z
date_updated: 2021-02-02T14:09:18Z
file_id: '9064'
file_name: thesis_pdfA2b.pdf
file_size: 5210329
relation: main_file
success: 1
file_date_updated: 2021-02-03T10:37:28Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '134'
place: Klosterneuburg
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '187'
relation: part_of_dissertation
status: public
- id: '8703'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
title: Multi-cover persistence and Delaunay mosaics
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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2021'
...
---
_id: '9317'
abstract:
- lang: eng
text: Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r
consists of all points in Rd 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 Rd+1 whose horizontal
integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module
of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant Agreement No. 78818 Alpha), and by the DFG Collaborative Research Center
TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant No. I02979-N35
of the Austrian Science Fund (FWF)\r\nOpen Access funding provided by the Institute
of Science and Technology (IST Austria)."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: 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
citation:
ama: Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls. Discrete
and Computational Geometry. 2021;65:1296–1313. doi:10.1007/s00454-021-00281-9
apa: Edelsbrunner, H., & Osang, G. F. (2021). The multi-cover persistence of
Euclidean balls. Discrete and Computational Geometry. Springer Nature.
https://doi.org/10.1007/s00454-021-00281-9
chicago: Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence
of Euclidean Balls.” Discrete and Computational Geometry. Springer Nature,
2021. https://doi.org/10.1007/s00454-021-00281-9.
ieee: H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean
balls,” Discrete and Computational Geometry, vol. 65. Springer Nature,
pp. 1296–1313, 2021.
ista: Edelsbrunner H, Osang GF. 2021. The multi-cover persistence of Euclidean balls.
Discrete and Computational Geometry. 65, 1296–1313.
mla: Edelsbrunner, Herbert, and Georg F. Osang. “The Multi-Cover Persistence of
Euclidean Balls.” Discrete and Computational Geometry, vol. 65, Springer
Nature, 2021, pp. 1296–1313, doi:10.1007/s00454-021-00281-9.
short: H. Edelsbrunner, G.F. Osang, Discrete and Computational Geometry 65 (2021)
1296–1313.
date_created: 2021-04-11T22:01:15Z
date_published: 2021-03-31T00:00:00Z
date_updated: 2023-08-07T14:35:44Z
day: '31'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-021-00281-9
ec_funded: 1
external_id:
isi:
- '000635460400001'
file:
- access_level: open_access
checksum: 59b4e1e827e494209bcb4aae22e1d347
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-01T10:56:53Z
date_updated: 2021-12-01T10:56:53Z
file_id: '10394'
file_name: 2021_DisCompGeo_Edelsbrunner_Osang.pdf
file_size: 677704
relation: main_file
success: 1
file_date_updated: 2021-12-01T10:56:53Z
has_accepted_license: '1'
intvolume: ' 65'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 1296–1313
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: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '187'
relation: earlier_version
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: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 65
year: '2021'
...
---
_id: '9465'
abstract:
- lang: eng
text: "Given a locally finite set \U0001D44B⊆ℝ\U0001D451 and an integer \U0001D458≥0,
we consider the function \U0001D430\U0001D458:Del\U0001D458(\U0001D44B)→ℝ on the
dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion
of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf
Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett
114:76–83, 2014). While this function is not necessarily generalized discrete
Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete
Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that
its increments can be meaningfully classified into critical and non-critical steps.
This result extends to the case of weighted points and sheds light on k-fold covers
with balls in Euclidean space."
article_number: '15'
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: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
citation:
ama: Edelsbrunner H, Nikitenko A, Osang GF. A step in the Delaunay mosaic of order
k. Journal of Geometry. 2021;112(1). doi:10.1007/s00022-021-00577-4
apa: Edelsbrunner, H., Nikitenko, A., & Osang, G. F. (2021). A step in the Delaunay
mosaic of order k. Journal of Geometry. Springer Nature. https://doi.org/10.1007/s00022-021-00577-4
chicago: Edelsbrunner, Herbert, Anton Nikitenko, and Georg F Osang. “A Step in the
Delaunay Mosaic of Order K.” Journal of Geometry. Springer Nature, 2021.
https://doi.org/10.1007/s00022-021-00577-4.
ieee: H. Edelsbrunner, A. Nikitenko, and G. F. Osang, “A step in the Delaunay mosaic
of order k,” Journal of Geometry, vol. 112, no. 1. Springer Nature, 2021.
ista: Edelsbrunner H, Nikitenko A, Osang GF. 2021. A step in the Delaunay mosaic
of order k. Journal of Geometry. 112(1), 15.
mla: Edelsbrunner, Herbert, et al. “A Step in the Delaunay Mosaic of Order K.” Journal
of Geometry, vol. 112, no. 1, 15, Springer Nature, 2021, doi:10.1007/s00022-021-00577-4.
short: H. Edelsbrunner, A. Nikitenko, G.F. Osang, Journal of Geometry 112 (2021).
date_created: 2021-06-06T22:01:29Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2022-05-12T11:41:45Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00022-021-00577-4
file:
- access_level: open_access
checksum: e52a832f1def52a2b23d21bcc09e646f
content_type: application/pdf
creator: kschuh
date_created: 2021-06-11T13:16:26Z
date_updated: 2021-06-11T13:16:26Z
file_id: '9544'
file_name: 2021_Geometry_Edelsbrunner.pdf
file_size: 694706
relation: main_file
success: 1
file_date_updated: 2021-06-11T13:16:26Z
has_accepted_license: '1'
intvolume: ' 112'
issue: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
publication: Journal of Geometry
publication_identifier:
eissn:
- '14208997'
issn:
- '00472468'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A step in the Delaunay mosaic 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2021'
...
---
_id: '9605'
abstract:
- lang: eng
text: 'Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within
distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter
family of spaces that grow larger when r increases or k decreases, called the
multicover bifiltration. Motivated by the problem of computing the homology of
this bifiltration, we introduce two closely related combinatorial bifiltrations,
one polyhedral and the other simplicial, which are both topologically equivalent
to the multicover bifiltration and far smaller than a Čech-based model considered
in prior work of Sheehy. Our polyhedral construction is a bifiltration of the
rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using
a variant of an algorithm given by these authors as well. Using an implementation
for dimension 2 and 3, we provide experimental results. Our simplicial construction
is useful for understanding the polyhedral construction and proving its correctness. '
acknowledgement: The authors want to thank the reviewers for many helpful comments
and suggestions.
alternative_title:
- LIPIcs
article_number: '27'
article_processing_charge: No
arxiv: 1
author:
- first_name: René
full_name: Corbet, René
last_name: Corbet
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
- first_name: Michael
full_name: Lesnick, Michael
last_name: Lesnick
- 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: 'Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration.
In: Leibniz International Proceedings in Informatics. Vol 189. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.27'
apa: 'Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2021). Computing
the multicover bifiltration. In Leibniz International Proceedings in Informatics
(Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.27'
chicago: Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing
the Multicover Bifiltration.” In Leibniz International Proceedings in Informatics,
Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.27.
ieee: R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover
bifiltration,” in Leibniz International Proceedings in Informatics, Online,
2021, vol. 189.
ista: 'Corbet R, Kerber M, Lesnick M, Osang GF. 2021. Computing the multicover bifiltration.
Leibniz International Proceedings in Informatics. SoCG: International Symposium
on Computational Geometry, LIPIcs, vol. 189, 27.'
mla: Corbet, René, et al. “Computing the Multicover Bifiltration.” Leibniz International
Proceedings in Informatics, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.27.
short: R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, in:, Leibniz International
Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2021.
conference:
end_date: 2021-06-11
location: Online
name: 'SoCG: International Symposium on Computational Geometry'
start_date: 2021-06-07
date_created: 2021-06-27T22:01:49Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-10-04T12:03:39Z
day: '02'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.27
external_id:
arxiv:
- '2103.07823'
file:
- access_level: open_access
checksum: 0de217501e7ba8b267d58deed0d51761
content_type: application/pdf
creator: cziletti
date_created: 2021-06-28T12:40:47Z
date_updated: 2021-06-28T12:40:47Z
file_id: '9610'
file_name: 2021_LIPIcs_Corbet.pdf
file_size: '1367983'
relation: main_file
success: 1
file_date_updated: 2021-06-28T12:40:47Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Leibniz International Proceedings in Informatics
publication_identifier:
isbn:
- '9783959771849'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
link:
- relation: extended_version
url: https://arxiv.org/abs/2103.07823
record:
- id: '12709'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Computing the multicover bifiltration
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '10204'
abstract:
- lang: eng
text: Two common representations of close packings of identical spheres consisting
of hexagonal layers, called Barlow stackings, appear abundantly in minerals and
metals. These motifs, however, occupy an identical portion of space and bear identical
first-order topological signatures as measured by persistent homology. Here we
present a novel method based on k-fold covers that unambiguously distinguishes
between these patterns. Moreover, our approach provides topological evidence that
the FCC motif is the more stable of the two in the context of evolving experimental
sphere packings during the transition from disordered to an ordered state. We
conclude that our approach can be generalised to distinguish between various Barlow
stackings manifested in minerals and metals.
acknowledgement: MS acknowledges the support by Australian Research Council funding
through the ARC Training Centre for M3D Innovation (IC180100008). MS thanks M. Hanifpour
and N. Francois for their input and valuable discussions. This project has received
funding from the European Research Council (ERC) under the European Union's Horizon
2020 research and innovation programme, grant no. 788183 and from the Wittgenstein
Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_processing_charge: No
article_type: original
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: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mohammad
full_name: Saadatfar, Mohammad
last_name: Saadatfar
citation:
ama: Osang GF, Edelsbrunner H, Saadatfar M. Topological signatures and stability
of hexagonal close packing and Barlow stackings. Soft Matter. 2021;17(40):9107-9115.
doi:10.1039/d1sm00774b
apa: Osang, G. F., Edelsbrunner, H., & Saadatfar, M. (2021). Topological signatures
and stability of hexagonal close packing and Barlow stackings. Soft Matter.
Royal Society of Chemistry . https://doi.org/10.1039/d1sm00774b
chicago: Osang, Georg F, Herbert Edelsbrunner, and Mohammad Saadatfar. “Topological
Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft
Matter. Royal Society of Chemistry , 2021. https://doi.org/10.1039/d1sm00774b.
ieee: G. F. Osang, H. Edelsbrunner, and M. Saadatfar, “Topological signatures and
stability of hexagonal close packing and Barlow stackings,” Soft Matter,
vol. 17, no. 40. Royal Society of Chemistry , pp. 9107–9115, 2021.
ista: Osang GF, Edelsbrunner H, Saadatfar M. 2021. Topological signatures and stability
of hexagonal close packing and Barlow stackings. Soft Matter. 17(40), 9107–9115.
mla: Osang, Georg F., et al. “Topological Signatures and Stability of Hexagonal
Close Packing and Barlow Stackings.” Soft Matter, vol. 17, no. 40, Royal
Society of Chemistry , 2021, pp. 9107–15, doi:10.1039/d1sm00774b.
short: G.F. Osang, H. Edelsbrunner, M. Saadatfar, Soft Matter 17 (2021) 9107–9115.
date_created: 2021-10-31T23:01:30Z
date_published: 2021-10-20T00:00:00Z
date_updated: 2023-10-03T09:24:27Z
day: '20'
ddc:
- '540'
department:
- _id: HeEd
doi: 10.1039/d1sm00774b
ec_funded: 1
external_id:
isi:
- '000700090000001'
pmid:
- '34569592'
file:
- access_level: open_access
checksum: b4da0c420530295e61b153960f6cb350
content_type: application/pdf
creator: dernst
date_created: 2023-10-03T09:21:42Z
date_updated: 2023-10-03T09:21:42Z
file_id: '14385'
file_name: 2021_SoftMatter_acceptedversion_Osang.pdf
file_size: 4678788
relation: main_file
success: 1
file_date_updated: 2023-10-03T09:21:42Z
has_accepted_license: '1'
intvolume: ' 17'
isi: 1
issue: '40'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 9107-9115
pmid: 1
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Soft Matter
publication_identifier:
eissn:
- 1744-6848
issn:
- 1744-683X
publication_status: published
publisher: 'Royal Society of Chemistry '
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topological signatures and stability of hexagonal close packing and Barlow
stackings
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '10367'
abstract:
- lang: eng
text: How information is created, shared and consumed has changed rapidly in recent
decades, in part thanks to new social platforms and technologies on the web. With
ever-larger amounts of unstructured and limited labels, organizing and reconciling
information from different sources and modalities is a central challenge in machine
learning. This cutting-edge tutorial aims to introduce the multimodal entailment
task, which can be useful for detecting semantic alignments when a single modality
alone does not suffice for a whole content understanding. Starting with a brief
overview of natural language processing, computer vision, structured data and
neural graph learning, we lay the foundations for the multimodal sections to follow.
We then discuss recent multimodal learning literature covering visual, audio and
language streams, and explore case studies focusing on tasks which require fine-grained
understanding of visual and linguistic semantics question answering, veracity
and hatred classification. Finally, we introduce a new dataset for recognizing
multimodal entailment, exploring it in a hands-on collaborative section. Overall,
this tutorial gives an overview of multimodal learning, introduces a multimodal
entailment dataset, and encourages future research in the topic.
acknowledgement: "We would like to thank Abby Schantz, Abe Ittycheriah, Aliaksei Severyn,
Allan Heydon, Aly\r\nGrealish, Andrey Vlasov, Arkaitz Zubiaga, Ashwin Kakarla, Chen
Sun, Clayton Williams, Cong\r\nYu, Cordelia Schmid, Da-Cheng Juan, Dan Finnie, Dani
Valevski, Daniel Rocha, David Price, David Sklar, Devi Krishna, Elena Kochkina,
Enrique Alfonseca, Franc¸oise Beaufays, Isabelle Augenstein, Jialu Liu, John Cantwell,
John Palowitch, Jordan Boyd-Graber, Lei Shi, Luis Valente, Maria Voitovich, Mehmet
Aktuna, Mogan Brown, Mor Naaman, Natalia P, Nidhi Hebbar, Pete Aykroyd, Rahul Sukthankar,
Richa Dixit, Steve Pucci, Tania Bedrax-Weiss, Tobias Kaufmann, Tom Boulos, Tu Tsao,
Vladimir Chtchetkine, Yair Kurzion, Yifan Xu and Zach Hynes."
article_processing_charge: No
author:
- first_name: Cesar
full_name: Ilharco, Cesar
last_name: Ilharco
- first_name: Afsaneh
full_name: Shirazi, Afsaneh
last_name: Shirazi
- first_name: Arjun
full_name: Gopalan, Arjun
last_name: Gopalan
- first_name: Arsha
full_name: Nagrani, Arsha
last_name: Nagrani
- first_name: Blaž
full_name: Bratanič, Blaž
last_name: Bratanič
- first_name: Chris
full_name: Bregler, Chris
last_name: Bregler
- first_name: Christina
full_name: Liu, Christina
last_name: Liu
- first_name: Felipe
full_name: Ferreira, Felipe
last_name: Ferreira
- first_name: Gabriek
full_name: Barcik, Gabriek
last_name: Barcik
- first_name: Gabriel
full_name: Ilharco, Gabriel
last_name: Ilharco
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
- first_name: Jannis
full_name: Bulian, Jannis
last_name: Bulian
- first_name: Jared
full_name: Frank, Jared
last_name: Frank
- first_name: Lucas
full_name: Smaira, Lucas
last_name: Smaira
- first_name: Qin
full_name: Cao, Qin
last_name: Cao
- first_name: Ricardo
full_name: Marino, Ricardo
last_name: Marino
- first_name: Roma
full_name: Patel, Roma
last_name: Patel
- first_name: Thomas
full_name: Leung, Thomas
last_name: Leung
- first_name: Vaiva
full_name: Imbrasaite, Vaiva
last_name: Imbrasaite
citation:
ama: 'Ilharco C, Shirazi A, Gopalan A, et al. Recognizing multimodal entailment.
In: 59th Annual Meeting of the Association for Computational Linguistics and
the 11th International Joint Conference on Natural Language Processing, Tutorial
Abstracts. Association for Computational Linguistics; 2021:29-30. doi:10.18653/v1/2021.acl-tutorials.6'
apa: 'Ilharco, C., Shirazi, A., Gopalan, A., Nagrani, A., Bratanič, B., Bregler,
C., … Imbrasaite, V. (2021). Recognizing multimodal entailment. In 59th Annual
Meeting of the Association for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing, Tutorial Abstracts (pp. 29–30).
Bangkok, Thailand: Association for Computational Linguistics. https://doi.org/10.18653/v1/2021.acl-tutorials.6'
chicago: Ilharco, Cesar, Afsaneh Shirazi, Arjun Gopalan, Arsha Nagrani, Blaž Bratanič,
Chris Bregler, Christina Liu, et al. “Recognizing Multimodal Entailment.” In 59th
Annual Meeting of the Association for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing, Tutorial Abstracts, 29–30.
Association for Computational Linguistics, 2021. https://doi.org/10.18653/v1/2021.acl-tutorials.6.
ieee: C. Ilharco et al., “Recognizing multimodal entailment,” in 59th
Annual Meeting of the Association for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing, Tutorial Abstracts, Bangkok,
Thailand, 2021, pp. 29–30.
ista: 'Ilharco C, Shirazi A, Gopalan A, Nagrani A, Bratanič B, Bregler C, Liu C,
Ferreira F, Barcik G, Ilharco G, Osang GF, Bulian J, Frank J, Smaira L, Cao Q,
Marino R, Patel R, Leung T, Imbrasaite V. 2021. Recognizing multimodal entailment.
59th Annual Meeting of the Association for Computational Linguistics and the 11th
International Joint Conference on Natural Language Processing, Tutorial Abstracts.
ACL: Association for Computational Linguistics ; IJCNLP: International Joint Conference
on Natural Language Processing, 29–30.'
mla: Ilharco, Cesar, et al. “Recognizing Multimodal Entailment.” 59th Annual
Meeting of the Association for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing, Tutorial Abstracts, Association
for Computational Linguistics, 2021, pp. 29–30, doi:10.18653/v1/2021.acl-tutorials.6.
short: C. Ilharco, A. Shirazi, A. Gopalan, A. Nagrani, B. Bratanič, C. Bregler,
C. Liu, F. Ferreira, G. Barcik, G. Ilharco, G.F. Osang, J. Bulian, J. Frank, L.
Smaira, Q. Cao, R. Marino, R. Patel, T. Leung, V. Imbrasaite, in:, 59th Annual
Meeting of the Association for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing, Tutorial Abstracts, Association
for Computational Linguistics, 2021, pp. 29–30.
conference:
end_date: 2021-08-06
location: Bangkok, Thailand
name: 'ACL: Association for Computational Linguistics ; IJCNLP: International Joint
Conference on Natural Language Processing'
start_date: 2021-08-01
date_created: 2021-11-28T23:01:30Z
date_published: 2021-08-01T00:00:00Z
date_updated: 2022-01-26T14:26:36Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.18653/v1/2021.acl-tutorials.6
file:
- access_level: open_access
checksum: b14052a025a6ecf675bdfe51db98c0d7
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-29T08:41:00Z
date_updated: 2021-11-29T08:41:00Z
file_id: '10368'
file_name: 2021_ACL_Ilharco.pdf
file_size: 1227703
relation: main_file
success: 1
file_date_updated: 2021-11-29T08:41:00Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://aclanthology.org/2021.acl-tutorials.6/
month: '08'
oa: 1
oa_version: Published Version
page: 29-30
publication: 59th Annual Meeting of the Association for Computational Linguistics
and the 11th International Joint Conference on Natural Language Processing, Tutorial
Abstracts
publication_identifier:
isbn:
- 9-781-9540-8557-2
publication_status: published
publisher: Association for Computational Linguistics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recognizing multimodal entailment
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '8703'
abstract:
- lang: eng
text: 'Even though Delaunay originally introduced his famous triangulations in the
case of infinite point sets with translational periodicity, a software that computes
such triangulations in the general case is not yet available, to the best of our
knowledge. Combining and generalizing previous work, we present a practical algorithm
for computing such triangulations. The algorithm has been implemented and experiments
show that its performance is as good as the one of the CGAL package, which is
restricted to cubic periodicity. '
alternative_title:
- LIPIcs
article_number: '75'
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: Mael
full_name: Rouxel-Labbé, Mael
last_name: Rouxel-Labbé
- first_name: Monique
full_name: Teillaud, Monique
last_name: Teillaud
citation:
ama: 'Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay
triangulations. In: 28th Annual European Symposium on Algorithms. Vol 173.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.75'
apa: 'Osang, G. F., Rouxel-Labbé, M., & Teillaud, M. (2020). Generalizing CGAL
periodic Delaunay triangulations. In 28th Annual European Symposium on Algorithms
(Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.75'
chicago: Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing
CGAL Periodic Delaunay Triangulations.” In 28th Annual European Symposium on
Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
https://doi.org/10.4230/LIPIcs.ESA.2020.75.
ieee: G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic
Delaunay triangulations,” in 28th Annual European Symposium on Algorithms,
Virtual, Online; Pisa, Italy, 2020, vol. 173.
ista: 'Osang GF, Rouxel-Labbé M, Teillaud M. 2020. Generalizing CGAL periodic Delaunay
triangulations. 28th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 173, 75.'
mla: Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.”
28th Annual European Symposium on Algorithms, vol. 173, 75, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.75.
short: G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-09-09
location: Virtual, Online; Pisa, Italy
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2020-09-07
date_created: 2020-10-25T23:01:18Z
date_published: 2020-08-26T00:00:00Z
date_updated: 2023-09-07T13:29:00Z
day: '26'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.ESA.2020.75
ec_funded: 1
file:
- access_level: open_access
checksum: fe0f7c49a99ed870c671b911e10d5496
content_type: application/pdf
creator: cziletti
date_created: 2020-10-27T14:31:52Z
date_updated: 2020-10-27T14:31:52Z
file_id: '8712'
file_name: 2020_LIPIcs_Osang.pdf
file_size: 733291
relation: main_file
success: 1
file_date_updated: 2020-10-27T14:31:52Z
has_accepted_license: '1'
intvolume: ' 173'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
publication: 28th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959771627'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '9056'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Generalizing CGAL periodic Delaunay triangulations
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 173
year: '2020'
...
---
_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: '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: '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'
...
---
_id: '1065'
abstract:
- lang: eng
text: 'We consider the problem of reachability in pushdown graphs. We study the
problem for pushdown graphs with constant treewidth. Even for pushdown graphs
with treewidth 1, for the reachability problem we establish the following: (i)
the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem
would contradict the k-clique conjecture and imply faster combinatorial algorithms
for cliques in graphs.'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- 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: Chatterjee K, Osang GF. Pushdown reachability with constant treewidth. Information
Processing Letters. 2017;122:25-29. doi:10.1016/j.ipl.2017.02.003
apa: Chatterjee, K., & Osang, G. F. (2017). Pushdown reachability with constant
treewidth. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2017.02.003
chicago: Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with
Constant Treewidth.” Information Processing Letters. Elsevier, 2017. https://doi.org/10.1016/j.ipl.2017.02.003.
ieee: K. Chatterjee and G. F. Osang, “Pushdown reachability with constant treewidth,”
Information Processing Letters, vol. 122. Elsevier, pp. 25–29, 2017.
ista: Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth.
Information Processing Letters. 122, 25–29.
mla: Chatterjee, Krishnendu, and Georg F. Osang. “Pushdown Reachability with Constant
Treewidth.” Information Processing Letters, vol. 122, Elsevier, 2017, pp.
25–29, doi:10.1016/j.ipl.2017.02.003.
short: K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:08:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
doi: 10.1016/j.ipl.2017.02.003
ec_funded: 1
external_id:
isi:
- '000399506600005'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2019-10-15T07:44:51Z
file_id: '4998'
file_name: IST-2018-991-v1+2_2018_Chatterjee_Pushdown_PREPRINT.pdf
file_size: 247657
relation: main_file
file_date_updated: 2019-10-15T07:44:51Z
has_accepted_license: '1'
intvolume: ' 122'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 25 - 29
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Information Processing Letters
publication_identifier:
issn:
- '00200190'
publication_status: published
publisher: Elsevier
publist_id: '6323'
pubrep_id: '991'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Pushdown reachability with constant treewidth
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 122
year: '2017'
...