---
_id: '15012'
abstract:
- lang: eng
text: We solve a problem of Dujmović and Wood (2007) by showing that a complete
convex geometric graph on n vertices cannot be decomposed into fewer than n-1
star-forests, each consisting of noncrossing edges. This bound is clearly tight.
We also discuss similar questions for abstract graphs.
acknowledgement: János Pach’s Research partially supported by European Research Council
(ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH),
grant K-131529. Work by Morteza Saghafian is partially supported by the European
Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian
Science Fund (FWF), grant No. Z 342-N31.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
- first_name: Patrick
full_name: Schnider, Patrick
last_name: Schnider
citation:
ama: 'Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests.
In: 31st International Symposium on Graph Drawing and Network Visualization.
Vol 14465. Springer Nature; 2024:339-346. doi:10.1007/978-3-031-49272-3_23'
apa: 'Pach, J., Saghafian, M., & Schnider, P. (2024). Decomposition of geometric
graphs into star-forests. In 31st International Symposium on Graph Drawing
and Network Visualization (Vol. 14465, pp. 339–346). Isola delle Femmine,
Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49272-3_23'
chicago: Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric
Graphs into Star-Forests.” In 31st International Symposium on Graph Drawing
and Network Visualization, 14465:339–46. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49272-3_23.
ieee: J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs
into star-forests,” in 31st International Symposium on Graph Drawing and Network
Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp.
339–346.
ista: 'Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs
into star-forests. 31st International Symposium on Graph Drawing and Network Visualization.
GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.'
mla: Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.”
31st International Symposium on Graph Drawing and Network Visualization,
vol. 14465, Springer Nature, 2024, pp. 339–46, doi:10.1007/978-3-031-49272-3_23.
short: J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on
Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346.
conference:
end_date: 2023-09-22
location: Isola delle Femmine, Palermo, Italy
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2023-09-20
date_created: 2024-02-18T23:01:03Z
date_published: 2024-01-01T00:00:00Z
date_updated: 2024-02-20T09:13:07Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-031-49272-3_23
ec_funded: 1
external_id:
arxiv:
- '2306.13201'
intvolume: ' 14465'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2306.13201
month: '01'
oa: 1
oa_version: Preprint
page: 339-346
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: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783031492716'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decomposition of geometric graphs into star-forests
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14465
year: '2024'
...
---
_id: '14345'
abstract:
- lang: eng
text: For a locally finite set in R2, the order-k Brillouin tessellations form an
infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely
dense and generic, then the corresponding infinite sequences of minimum and maximum
angles are both monotonic in k. As an example, a stationary Poisson point process
in R2 is locally finite, coarsely dense, and generic with probability one. For
such a set, the distributions of angles in the Voronoi tessellations, Delaunay
mosaics, and Brillouin tessellations are independent of the order and can be derived
from the formula for angles in order-1 Delaunay mosaics given by Miles (Math.
Biosci. 6, 85–127 (1970)).
acknowledgement: Work by all authors but A. Garber is supported by the European Research
Council (ERC), Grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund
(FWF), Grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109,
Austrian Science Fund (FWF), Grant No. I 02979-N35. Work by A. Garber is partially
supported by the Alexander von Humboldt Foundation.
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: Alexey
full_name: Garber, Alexey
last_name: Garber
- first_name: Mohadese
full_name: Ghafari, Mohadese
last_name: Ghafari
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. On angles in higher
order Brillouin tessellations and related tilings in the plane. Discrete and
Computational Geometry. 2023. doi:10.1007/s00454-023-00566-1
apa: Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2023).
On angles in higher order Brillouin tessellations and related tilings in the plane.
Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00566-1
chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and
Morteza Saghafian. “On Angles in Higher Order Brillouin Tessellations and Related
Tilings in the Plane.” Discrete and Computational Geometry. Springer Nature,
2023. https://doi.org/10.1007/s00454-023-00566-1.
ieee: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “On angles
in higher order Brillouin tessellations and related tilings in the plane,” Discrete
and Computational Geometry. Springer Nature, 2023.
ista: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2023. On angles
in higher order Brillouin tessellations and related tilings in the plane. Discrete
and Computational Geometry.
mla: Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations
and Related Tilings in the Plane.” Discrete and Computational Geometry,
Springer Nature, 2023, doi:10.1007/s00454-023-00566-1.
short: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete
and Computational Geometry (2023).
date_created: 2023-09-17T22:01:10Z
date_published: 2023-09-07T00:00:00Z
date_updated: 2023-12-13T12:25:06Z
day: '07'
department:
- _id: HeEd
doi: 10.1007/s00454-023-00566-1
ec_funded: 1
external_id:
arxiv:
- '2204.01076'
isi:
- '001060727600004'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00454-023-00566-1
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _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: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On angles in higher order Brillouin tessellations and related tilings in the
plane
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '13182'
abstract:
- lang: eng
text: "We characterize critical points of 1-dimensional maps paired in persistent
homology\r\ngeometrically and this way get elementary proofs of theorems about
the symmetry\r\nof persistence diagrams and the variation of such maps. In particular,
we identify\r\nbranching points and endpoints of networks as the sole source of
asymmetry and\r\nrelate the cycle basis in persistent homology with a version
of the stable marriage\r\nproblem. Our analysis provides the foundations of fast
algorithms for maintaining a\r\ncollection of sorted lists together with its persistence
diagram."
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. The authors of
this paper thank anonymous reviewers for their constructive criticism and Monika
Henzinger for detailed comments on an earlier version of this paper.
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Sebastiano
full_name: Cultrera Di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera Di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Geometric characterization
of the persistence of 1D maps. Journal of Applied and Computational Topology.
2023. doi:10.1007/s41468-023-00126-9
apa: Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M.
(2023). Geometric characterization of the persistence of 1D maps. Journal of
Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-023-00126-9
chicago: Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
and Morteza Saghafian. “Geometric Characterization of the Persistence of 1D Maps.”
Journal of Applied and Computational Topology. Springer Nature, 2023. https://doi.org/10.1007/s41468-023-00126-9.
ieee: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Geometric
characterization of the persistence of 1D maps,” Journal of Applied and Computational
Topology. Springer Nature, 2023.
ista: Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2023. Geometric
characterization of the persistence of 1D maps. Journal of Applied and Computational
Topology.
mla: Biswas, Ranita, et al. “Geometric Characterization of the Persistence of 1D
Maps.” Journal of Applied and Computational Topology, Springer Nature,
2023, doi:10.1007/s41468-023-00126-9.
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal
of Applied and Computational Topology (2023).
date_created: 2023-07-02T22:00:44Z
date_published: 2023-06-17T00:00:00Z
date_updated: 2023-10-18T08:13:10Z
day: '17'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s41468-023-00126-9
ec_funded: 1
file:
- access_level: open_access
checksum: 697249d5d1c61dea4410b9f021b70fce
content_type: application/pdf
creator: alisjak
date_created: 2023-07-03T09:41:05Z
date_updated: 2023-07-03T09:41:05Z
file_id: '13185'
file_name: 2023_Journal of Applied and Computational Topology_Biswas.pdf
file_size: 487355
relation: main_file
success: 1
file_date_updated: 2023-07-03T09:41:05Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Discretization in Geometry and Dynamics
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Geometric characterization of the persistence of 1D maps
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
year: '2023'
...
---
_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: '12544'
abstract:
- lang: eng
text: Geometry is crucial in our efforts to comprehend the structures and dynamics
of biomolecules. For example, volume, surface area, and integrated mean and Gaussian
curvature of the union of balls representing a molecule are used to quantify its
interactions with the water surrounding it in the morphometric implicit solvent
models. The Alpha Shape theory provides an accurate and reliable method for computing
these geometric measures. In this paper, we derive homogeneous formulas for the
expressions of these measures and their derivatives with respect to the atomic
coordinates, and we provide algorithms that implement them into a new software
package, AlphaMol. The only variables in these formulas are the interatomic distances,
making them insensitive to translations and rotations. AlphaMol includes a sequential
algorithm and a parallel algorithm. In the parallel version, we partition the
atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree
algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented
by a buffer zone to account for atoms whose ball representations may partially
cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up
compared to an independent serial implementation when using 32 processors. For
instance, it takes 31 s to compute the geometric measures and derivatives of each
atom in a viral capsid with more than 26 million atoms on 32 Intel processors
running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant
computations, which ultimately limit the impact of using multiple processors.
AlphaMol is available as an OpenSource software.
acknowledgement: "P.K. acknowledges support from the University of California Multicampus
Research Programs and Initiatives (Grant No. M21PR3267) and from the NSF (Grant
No.1760485). H.E. acknowledges support from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program, 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.\r\nOpen Access
is funded by the Austrian Science Fund (FWF)."
article_processing_charge: No
article_type: original
author:
- first_name: Patrice
full_name: Koehl, Patrice
last_name: Koehl
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Koehl P, Akopyan A, Edelsbrunner H. Computing the volume, surface area, mean,
and Gaussian curvatures of molecules and their derivatives. Journal of Chemical
Information and Modeling. 2023;63(3):973-985. doi:10.1021/acs.jcim.2c01346
apa: Koehl, P., Akopyan, A., & Edelsbrunner, H. (2023). Computing the volume,
surface area, mean, and Gaussian curvatures of molecules and their derivatives.
Journal of Chemical Information and Modeling. American Chemical Society.
https://doi.org/10.1021/acs.jcim.2c01346
chicago: Koehl, Patrice, Arseniy Akopyan, and Herbert Edelsbrunner. “Computing the
Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.”
Journal of Chemical Information and Modeling. American Chemical Society,
2023. https://doi.org/10.1021/acs.jcim.2c01346.
ieee: P. Koehl, A. Akopyan, and H. Edelsbrunner, “Computing the volume, surface
area, mean, and Gaussian curvatures of molecules and their derivatives,” Journal
of Chemical Information and Modeling, vol. 63, no. 3. American Chemical Society,
pp. 973–985, 2023.
ista: Koehl P, Akopyan A, Edelsbrunner H. 2023. Computing the volume, surface area,
mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical
Information and Modeling. 63(3), 973–985.
mla: Koehl, Patrice, et al. “Computing the Volume, Surface Area, Mean, and Gaussian
Curvatures of Molecules and Their Derivatives.” Journal of Chemical Information
and Modeling, vol. 63, no. 3, American Chemical Society, 2023, pp. 973–85,
doi:10.1021/acs.jcim.2c01346.
short: P. Koehl, A. Akopyan, H. Edelsbrunner, Journal of Chemical Information and
Modeling 63 (2023) 973–985.
date_created: 2023-02-12T23:00:59Z
date_published: 2023-02-13T00:00:00Z
date_updated: 2023-08-16T12:22:07Z
day: '13'
ddc:
- '510'
- '540'
department:
- _id: HeEd
doi: 10.1021/acs.jcim.2c01346
ec_funded: 1
external_id:
isi:
- '000920370700001'
pmid:
- '36638318'
file:
- access_level: open_access
checksum: 7d20562269edff1e31b9d6019d4983b0
content_type: application/pdf
creator: dernst
date_created: 2023-08-16T12:21:13Z
date_updated: 2023-08-16T12:21:13Z
file_id: '14070'
file_name: 2023_JCIM_Koehl.pdf
file_size: 8069223
relation: main_file
success: 1
file_date_updated: 2023-08-16T12:21:13Z
has_accepted_license: '1'
intvolume: ' 63'
isi: 1
issue: '3'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 973-985
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
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Journal of Chemical Information and Modeling
publication_identifier:
eissn:
- 1549-960X
issn:
- 1549-9596
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing the volume, surface area, mean, and Gaussian curvatures of molecules
and their derivatives
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: 63
year: '2023'
...
---
_id: '11658'
abstract:
- lang: eng
text: The depth of a cell in an arrangement of n (non-vertical) great-spheres in
Sd is the number of great-spheres that pass above the cell. We prove Euler-type
relations, which imply extensions of the classic Dehn–Sommerville relations for
convex polytopes to sublevel sets of the depth function, and we use the relations
to extend the expressions for the number of faces of neighborly polytopes to the
number of cells of levels in neighborly arrangements.
acknowledgement: 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: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Depth in arrangements:
Dehn–Sommerville–Euler relations with applications. Leibniz International Proceedings
on Mathematics.'
apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian,
M. (n.d.). Depth in arrangements: Dehn–Sommerville–Euler relations with applications.
Leibniz International Proceedings on Mathematics. Schloss Dagstuhl - Leibniz
Zentrum für Informatik.'
chicago: 'Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
and Morteza Saghafian. “Depth in Arrangements: Dehn–Sommerville–Euler Relations
with Applications.” Leibniz International Proceedings on Mathematics. Schloss
Dagstuhl - Leibniz Zentrum für Informatik, n.d.'
ieee: 'R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Depth
in arrangements: Dehn–Sommerville–Euler relations with applications,” Leibniz
International Proceedings on Mathematics. Schloss Dagstuhl - Leibniz Zentrum
für Informatik.'
ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Depth in
arrangements: Dehn–Sommerville–Euler relations with applications. Leibniz International
Proceedings on Mathematics.'
mla: 'Biswas, Ranita, et al. “Depth in Arrangements: Dehn–Sommerville–Euler Relations
with Applications.” Leibniz International Proceedings on Mathematics, Schloss
Dagstuhl - Leibniz Zentrum für Informatik.'
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Leibniz
International Proceedings on Mathematics (n.d.).
date_created: 2022-07-27T09:27:34Z
date_published: 2022-07-27T00:00:00Z
date_updated: 2022-07-28T07:57:48Z
day: '27'
ddc:
- '510'
department:
- _id: GradSch
- _id: HeEd
ec_funded: 1
file:
- access_level: open_access
checksum: b2f511e8b1cae5f1892b0cdec341acac
content_type: application/pdf
creator: scultrer
date_created: 2022-07-27T09:25:53Z
date_updated: 2022-07-27T09:25:53Z
file_id: '11659'
file_name: D-S-E.pdf
file_size: 639266
relation: main_file
file_date_updated: 2022-07-27T09:25:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Leibniz International Proceedings on Mathematics
publication_status: submitted
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'Depth in arrangements: Dehn–Sommerville–Euler relations with applications'
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
year: '2022'
...
---
_id: '11660'
abstract:
- lang: eng
text: 'We characterize critical points of 1-dimensional maps paired in persistent
homology geometrically and this way get elementary proofs of theorems about the
symmetry of persistence diagrams and the variation of such maps. In particular,
we identify branching points and endpoints of networks as the sole source of asymmetry
and relate the cycle basis in persistent homology with a version of the stable
marriage problem. Our analysis provides the foundations of fast algorithms for
maintaining collections of interrelated sorted lists together with their persistence
diagrams. '
acknowledgement: '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. '
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
last_name: Saghafian
citation:
ama: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. A window to
the persistence of 1D maps. I: Geometric characterization of critical point pairs.
LIPIcs.'
apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian,
M. (n.d.). A window to the persistence of 1D maps. I: Geometric characterization
of critical point pairs. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik.'
chicago: 'Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
and Morteza Saghafian. “A Window to the Persistence of 1D Maps. I: Geometric Characterization
of Critical Point Pairs.” LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, n.d.'
ieee: 'R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “A
window to the persistence of 1D maps. I: Geometric characterization of critical
point pairs,” LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.'
ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. A window
to the persistence of 1D maps. I: Geometric characterization of critical point
pairs. LIPIcs.'
mla: 'Biswas, Ranita, et al. “A Window to the Persistence of 1D Maps. I: Geometric
Characterization of Critical Point Pairs.” LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik.'
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, LIPIcs
(n.d.).
date_created: 2022-07-27T09:31:15Z
date_published: 2022-07-25T00:00:00Z
date_updated: 2022-07-28T08:05:34Z
day: '25'
ddc:
- '510'
department:
- _id: GradSch
- _id: HeEd
ec_funded: 1
file:
- access_level: open_access
checksum: 95903f9d1649e8e437a967b6f2f64730
content_type: application/pdf
creator: scultrer
date_created: 2022-07-27T09:30:30Z
date_updated: 2022-07-27T09:30:30Z
file_id: '11661'
file_name: window 1.pdf
file_size: 564836
relation: main_file
file_date_updated: 2022-07-27T09:30:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: LIPIcs
publication_status: submitted
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'A window to the persistence of 1D maps. I: Geometric characterization of critical
point pairs'
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
year: '2022'
...
---
_id: '10208'
abstract:
- lang: eng
text: It is practical to collect a huge amount of movement data and environmental
context information along with the health signals of individuals because there
is the emergence of new generations of positioning and tracking technologies and
rapid advancements of health sensors. The study of the relations between these
datasets and their sequence similarity analysis is of interest to many applications
such as health monitoring and recommender systems. However, entering all movement
parameters and health signals can lead to the complexity of the problem and an
increase in its computational load. In this situation, dimension reduction techniques
can be used to avoid consideration of simultaneous dependent parameters in the
process of similarity measurement of the trajectories. The present study provides
a framework, named CaDRAW, to use spatial–temporal data and movement parameters
along with independent context information in the process of measuring the similarity
of trajectories. In this regard, the omission of dependent movement characteristic
signals is conducted by using an unsupervised feature selection dimension reduction
technique. To evaluate the effectiveness of the proposed framework, it was applied
to a real contextualized movement and related health signal datasets of individuals.
The results indicated the capability of the proposed framework in measuring the
similarity and in decreasing the characteristic signals in such a way that the
similarity results -before and after reduction of dependent characteristic signals-
have small differences. The mean differences between the obtained results before
and after reducing the dimension were 0.029 and 0.023 for the round path, respectively.
acknowledgement: The third author acknowledges the funding received from the Wittgenstein
Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_processing_charge: No
article_type: original
author:
- first_name: Samira
full_name: Goudarzi, Samira
last_name: Goudarzi
- first_name: Mohammad
full_name: Sharif, Mohammad
last_name: Sharif
- first_name: Farid
full_name: Karimipour, Farid
id: 2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425
last_name: Karimipour
orcid: 0000-0001-6746-4174
citation:
ama: Goudarzi S, Sharif M, Karimipour F. A context-aware dimension reduction framework
for trajectory and health signal analyses. Journal of Ambient Intelligence
and Humanized Computing. 2022;13:2621–2635. doi:10.1007/s12652-021-03569-z
apa: Goudarzi, S., Sharif, M., & Karimipour, F. (2022). A context-aware dimension
reduction framework for trajectory and health signal analyses. Journal of Ambient
Intelligence and Humanized Computing. Springer Nature. https://doi.org/10.1007/s12652-021-03569-z
chicago: Goudarzi, Samira, Mohammad Sharif, and Farid Karimipour. “A Context-Aware
Dimension Reduction Framework for Trajectory and Health Signal Analyses.” Journal
of Ambient Intelligence and Humanized Computing. Springer Nature, 2022. https://doi.org/10.1007/s12652-021-03569-z.
ieee: S. Goudarzi, M. Sharif, and F. Karimipour, “A context-aware dimension reduction
framework for trajectory and health signal analyses,” Journal of Ambient Intelligence
and Humanized Computing, vol. 13. Springer Nature, pp. 2621–2635, 2022.
ista: Goudarzi S, Sharif M, Karimipour F. 2022. A context-aware dimension reduction
framework for trajectory and health signal analyses. Journal of Ambient Intelligence
and Humanized Computing. 13, 2621–2635.
mla: Goudarzi, Samira, et al. “A Context-Aware Dimension Reduction Framework for
Trajectory and Health Signal Analyses.” Journal of Ambient Intelligence and
Humanized Computing, vol. 13, Springer Nature, 2022, pp. 2621–2635, doi:10.1007/s12652-021-03569-z.
short: S. Goudarzi, M. Sharif, F. Karimipour, Journal of Ambient Intelligence and
Humanized Computing 13 (2022) 2621–2635.
date_created: 2021-11-02T09:28:55Z
date_published: 2022-05-01T00:00:00Z
date_updated: 2023-08-02T13:31:48Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s12652-021-03569-z
external_id:
isi:
- '000712198000001'
file:
- access_level: open_access
checksum: 0a8961416a9bb2be5a1cebda65468bcf
content_type: application/pdf
creator: fkarimip
date_created: 2021-11-12T19:38:05Z
date_updated: 2022-12-20T23:30:08Z
embargo: 2022-11-12
file_id: '10279'
file_name: A Context‑aware Dimension Reduction Framework - Journal of Ambient Intelligence
2021 (Preprint version).pdf
file_size: 1634958
relation: main_file
file_date_updated: 2022-12-20T23:30:08Z
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
keyword:
- general computer science
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 2621–2635
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Journal of Ambient Intelligence and Humanized Computing
publication_identifier:
eissn:
- 1868-5145
issn:
- 1868-5137
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A context-aware dimension reduction framework for trajectory and health signal
analyses
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13
year: '2022'
...
---
_id: '11938'
abstract:
- lang: eng
text: A matching is compatible to two or more labeled point sets of size n with
labels {1, . . . , n} if its straight-line drawing on each of these point sets
is crossing-free. We study the maximum number of edges in a matching compatible
to two or more labeled point sets in general position in the plane. We show that
for any two labeled sets of n points in convex position there exists a compatible
matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets
we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound,
we use probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1))
edges. Finally, we show that Θ(log n) copies of any set of n points are necessary
and sufficient for the existence of labelings of these point sets such that any
compatible matching consists only of a single edge.
acknowledgement: 'A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- 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: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591
apa: Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph
Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” Journal of Graph Algorithms and Applications. Brown University,
2022. https://doi.org/10.7155/jgaa.00591.
ieee: O. Aichholzer et al., “On compatible matchings,” Journal of Graph
Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240,
2022.
ista: Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and
Applications. 26(2), 225–240.
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms
and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022)
225–240.
date_created: 2022-08-21T22:01:56Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-23T13:54:21Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.7155/jgaa.00591
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
file:
- access_level: open_access
checksum: dc6e255e3558faff924fd9e370886c11
content_type: application/pdf
creator: dernst
date_created: 2022-08-22T06:42:42Z
date_updated: 2022-08-22T06:42:42Z
file_id: '11940'
file_name: 2022_JourGraphAlgorithmsApplic_Aichholzer.pdf
file_size: 694538
relation: main_file
success: 1
file_date_updated: 2022-08-22T06:42:42Z
has_accepted_license: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 225-240
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '9296'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
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: 26
year: '2022'
...
---
_id: '8317'
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 one or several
holes to fold into a cube, and conditions under which cube folding is impossible.
In particular, we show that all but five special “basic” holes guarantee foldability.
acknowledgement: This research was performed in part at the 33rd Bellairs Winter Workshop
on Computational Geometry. We thank all other participants for a fruitful atmosphere.
H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially
funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_number: '101700'
article_processing_charge: No
article_type: original
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: Sándor P.
full_name: Fekete, Sándor 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. Computational Geometry: Theory and Applications. 2021;93.
doi:10.1016/j.comgeo.2020.101700'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a
cube. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2020.101700'
chicago: 'Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine,
Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes
with Holes into a Cube.” Computational Geometry: Theory and Applications.
Elsevier, 2021. https://doi.org/10.1016/j.comgeo.2020.101700.'
ieee: 'O. Aichholzer et al., “Folding polyominoes with holes into a cube,”
Computational Geometry: Theory and Applications, vol. 93. Elsevier, 2021.'
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. 2021. Folding
polyominoes with holes into a cube. Computational Geometry: Theory and Applications.
93, 101700.'
mla: 'Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational
Geometry: Theory and Applications, vol. 93, 101700, Elsevier, 2021, doi:10.1016/j.comgeo.2020.101700.'
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,
Computational Geometry: Theory and Applications 93 (2021).'
date_created: 2020-08-30T22:01:09Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2023-08-04T10:57:42Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2020.101700
external_id:
arxiv:
- '1910.09917'
isi:
- '000579185100004'
intvolume: ' 93'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.09917v3
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- '09257721'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '6989'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 93
year: '2021'
...
---
_id: '9296'
abstract:
- lang: eng
text: ' matching is compatible to two or more labeled point sets of size n with
labels {1,…,n} if its straight-line drawing on each of these point sets is
crossing-free. We study the maximum number of edges in a matching compatible to
two or more labeled point sets in general position in the plane. We show that
for any two labeled convex sets of n points there exists a compatible matching
with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct
compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use
probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges.
Finally, we show that Θ(logn) copies of any set of n points are necessary and
sufficient for the existence of a labeling such that any compatible matching consists
only of a single edge.'
acknowledgement: 'A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- 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: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
In: 15th International Conference on Algorithms and Computation. Vol 12635.
Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18'
apa: 'Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International
Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon,
Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18'
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” In 15th International Conference on Algorithms and Computation,
12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.
ieee: O. Aichholzer et al., “On compatible matchings,” in 15th International
Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635,
pp. 221–233.
ista: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference
on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol.
12635, 221–233.'
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International
Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021,
pp. 221–33, doi:10.1007/978-3-030-68211-8_18.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and
Computation, Springer Nature, 2021, pp. 221–233.
conference:
end_date: 2021-03-02
location: Yangon, Myanmar
name: 'WALCOM: Algorithms and Computation'
start_date: 2021-02-28
date_created: 2021-03-28T22:01:41Z
date_published: 2021-02-16T00:00:00Z
date_updated: 2023-02-21T16:33:44Z
day: '16'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.1007/978-3-030-68211-8_18
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
intvolume: ' 12635'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.03928
month: '02'
oa: 1
oa_version: Preprint
page: 221-233
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: 15th International Conference on Algorithms and Computation
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030682101'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11938'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 12635
year: '2021'
...
---
_id: '9602'
abstract:
- lang: eng
text: "An ordered graph is a graph with a linear ordering on its vertex set. We
prove that for every positive integer k, there exists a constant ck > 0 such that
any ordered graph G on n vertices with the property that neither G nor its complement
contains an induced monotone path of size k, has either a clique or an independent
set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and
Thomassé, who proved the analogous result for unordered graphs.\r\nA key idea
of the above paper was to show that any unordered graph on n vertices that does
not contain an induced path of size k, and whose maximum degree is at most c(k)n
for some small c(k) > 0, contains two disjoint linear size subsets with no edge
between them. This approach fails for ordered graphs, because the analogous statement
is false for k ≥ 3, by a construction of Fox. We provide some further examples
showing that this statement also fails for ordered graphs avoiding other ordered
trees."
acknowledgement: We would like to thank the anonymous referees for their useful comments
and suggestions. János Pach is partially supported by Austrian Science Fund (FWF)
grant Z 342-N31 and by ERC Advanced grant “GeoScape.” István Tomon is partially
supported by Swiss National Science Foundation grant no. 200021_196965, and thanks
the support of MIPT Moscow. Both authors are partially supported by The Russian
Government in the framework of MegaGrant no. 075-15-2019-1926.
article_processing_charge: No
article_type: original
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: István
full_name: Tomon, István
last_name: Tomon
citation:
ama: Pach J, Tomon I. Erdős-Hajnal-type results for monotone paths. Journal of
Combinatorial Theory Series B. 2021;151:21-37. doi:10.1016/j.jctb.2021.05.004
apa: Pach, J., & Tomon, I. (2021). Erdős-Hajnal-type results for monotone paths.
Journal of Combinatorial Theory. Series B. Elsevier. https://doi.org/10.1016/j.jctb.2021.05.004
chicago: Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone
Paths.” Journal of Combinatorial Theory. Series B. Elsevier, 2021. https://doi.org/10.1016/j.jctb.2021.05.004.
ieee: J. Pach and I. Tomon, “Erdős-Hajnal-type results for monotone paths,” Journal
of Combinatorial Theory. Series B, vol. 151. Elsevier, pp. 21–37, 2021.
ista: Pach J, Tomon I. 2021. Erdős-Hajnal-type results for monotone paths. Journal
of Combinatorial Theory. Series B. 151, 21–37.
mla: Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.”
Journal of Combinatorial Theory. Series B, vol. 151, Elsevier, 2021, pp.
21–37, doi:10.1016/j.jctb.2021.05.004.
short: J. Pach, I. Tomon, Journal of Combinatorial Theory. Series B 151 (2021) 21–37.
date_created: 2021-06-27T22:01:47Z
date_published: 2021-06-09T00:00:00Z
date_updated: 2023-08-10T13:38:00Z
day: '09'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jctb.2021.05.004
external_id:
isi:
- '000702280800002'
file:
- access_level: open_access
checksum: 15fbc9064cd9d1c777ac0043b78c8f12
content_type: application/pdf
creator: asandaue
date_created: 2021-06-28T13:33:23Z
date_updated: 2021-06-28T13:33:23Z
file_id: '9612'
file_name: 2021_JournalOfCombinatorialTheory_Pach.pdf
file_size: 418168
relation: main_file
success: 1
file_date_updated: 2021-06-28T13:33:23Z
has_accepted_license: '1'
intvolume: ' 151'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 21-37
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Journal of Combinatorial Theory. Series B
publication_identifier:
issn:
- 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Erdős-Hajnal-type results for monotone paths
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: 151
year: '2021'
...
---
_id: '9604'
abstract:
- lang: eng
text: Generalizing Lee’s inductive argument for counting the cells of higher order
Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse
theoretic quantities for piecewise constant functions on planar arrangements.
Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number
of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for
1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s
first k-1 sublevel sets. We get similar expressions for the vertices, edges, and
polygons of the order-k Voronoi tessellation.
alternative_title:
- LIPIcs
article_number: '16'
article_processing_charge: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
last_name: Saghafian
citation:
ama: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells
of order-k voronoi tessellations in ℝ3 with morse theory. In: Leibniz
International Proceedings in Informatics. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.16'
apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian,
M. (2021). Counting cells of order-k voronoi tessellations in ℝ3 with
morse theory. In Leibniz International Proceedings in Informatics (Vol.
189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.16'
chicago: Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ3
with Morse Theory.” In Leibniz International Proceedings in Informatics,
Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.16.
ieee: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting
cells of order-k voronoi tessellations in ℝ3 with morse theory,” in
Leibniz International Proceedings in Informatics, Online, 2021, vol. 189.
ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting
cells of order-k voronoi tessellations in ℝ3 with morse theory. Leibniz
International Proceedings in Informatics. SoCG: International Symposium on Computational
Geometry, LIPIcs, vol. 189, 16.'
mla: Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in
ℝ3 with Morse Theory.” Leibniz International Proceedings in Informatics,
vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.16.
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, 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:48Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-02-23T14:02:28Z
day: '02'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.16
ec_funded: 1
file:
- access_level: open_access
checksum: 22b11a719018b22ecba2471b51f2eb40
content_type: application/pdf
creator: asandaue
date_created: 2021-06-28T13:11:39Z
date_updated: 2021-06-28T13:11:39Z
file_id: '9611'
file_name: 2021_LIPIcs_Biswas.pdf
file_size: 727817
relation: main_file
success: 1
file_date_updated: 2021-06-28T13:11:39Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Discretization in Geometry and Dynamics
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'
scopus_import: '1'
status: public
title: Counting cells of order-k voronoi tessellations in ℝ3 with morse
theory
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: '10222'
abstract:
- lang: eng
text: Consider a random set of points on the unit sphere in ℝd, which can be either
uniformly sampled or a Poisson point process. Its convex hull is a random inscribed
polytope, whose boundary approximates the sphere. We focus on the case d = 3,
for which there are elementary proofs and fascinating formulas for metric properties.
In particular, we study the fraction of acute facets, the expected intrinsic volumes,
the total edge length, and the distance to a fixed point. Finally we generalize
the results to the ellipsoid with homeoid density.
acknowledgement: "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.\r\nWe
are grateful to Dmitry Zaporozhets and Christoph Thäle for valuable comments and
for directing us to relevant references. We also thank to Anton Mellit for a useful
discussion on Bessel functions."
article_processing_charge: Yes (via OA deal)
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: 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: Akopyan A, Edelsbrunner H, Nikitenko A. The beauty of random polytopes inscribed
in the 2-sphere. Experimental Mathematics. 2021:1-15. doi:10.1080/10586458.2021.1980459
apa: Akopyan, A., Edelsbrunner, H., & Nikitenko, A. (2021). The beauty of random
polytopes inscribed in the 2-sphere. Experimental Mathematics. Taylor and
Francis. https://doi.org/10.1080/10586458.2021.1980459
chicago: Akopyan, Arseniy, Herbert Edelsbrunner, and Anton Nikitenko. “The Beauty
of Random Polytopes Inscribed in the 2-Sphere.” Experimental Mathematics.
Taylor and Francis, 2021. https://doi.org/10.1080/10586458.2021.1980459.
ieee: A. Akopyan, H. Edelsbrunner, and A. Nikitenko, “The beauty of random polytopes
inscribed in the 2-sphere,” Experimental Mathematics. Taylor and Francis,
pp. 1–15, 2021.
ista: Akopyan A, Edelsbrunner H, Nikitenko A. 2021. The beauty of random polytopes
inscribed in the 2-sphere. Experimental Mathematics., 1–15.
mla: Akopyan, Arseniy, et al. “The Beauty of Random Polytopes Inscribed in the 2-Sphere.”
Experimental Mathematics, Taylor and Francis, 2021, pp. 1–15, doi:10.1080/10586458.2021.1980459.
short: A. Akopyan, H. Edelsbrunner, A. Nikitenko, Experimental Mathematics (2021)
1–15.
date_created: 2021-11-07T23:01:25Z
date_published: 2021-10-25T00:00:00Z
date_updated: 2023-08-14T11:57:07Z
day: '25'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1080/10586458.2021.1980459
ec_funded: 1
external_id:
arxiv:
- '2007.07783'
isi:
- '000710893500001'
file:
- access_level: open_access
checksum: 3514382e3a1eb87fa6c61ad622874415
content_type: application/pdf
creator: dernst
date_created: 2023-08-14T11:55:10Z
date_updated: 2023-08-14T11:55:10Z
file_id: '14053'
file_name: 2023_ExperimentalMath_Akopyan.pdf
file_size: 1966019
relation: main_file
success: 1
file_date_updated: 2023-08-14T11:55:10Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '10'
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: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Discretization in Geometry and Dynamics
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Experimental Mathematics
publication_identifier:
eissn:
- 1944-950X
issn:
- 1058-6458
publication_status: published
publisher: Taylor and Francis
quality_controlled: '1'
scopus_import: '1'
status: public
title: The beauty of random polytopes inscribed in the 2-sphere
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
year: '2021'
...
---
_id: '7962'
abstract:
- lang: eng
text: 'A string graph is the intersection graph of a family of continuous arcs in
the plane. The intersection graph of a family of plane convex sets is a string
graph, but not all string graphs can be obtained in this way. We prove the following
structure theorem conjectured by Janson and Uzzell: The vertex set of almost all
string graphs on n vertices can be partitioned into five cliques such that some
pair of them is not connected by any edge (n→∞). We also show that every graph
with the above property is an intersection graph of plane convex sets. As a corollary,
we obtain that almost all string graphs on n vertices are intersection graphs
of plane convex sets.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Bruce
full_name: Reed, Bruce
last_name: Reed
- first_name: Yelena
full_name: Yuditsky, Yelena
last_name: Yuditsky
citation:
ama: Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs
of plane convex sets. Discrete and Computational Geometry. 2020;63(4):888-917.
doi:10.1007/s00454-020-00213-z
apa: Pach, J., Reed, B., & Yuditsky, Y. (2020). Almost all string graphs are
intersection graphs of plane convex sets. Discrete and Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-020-00213-z
chicago: Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs
Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry.
Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00213-z.
ieee: J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection
graphs of plane convex sets,” Discrete and Computational Geometry, vol.
63, no. 4. Springer Nature, pp. 888–917, 2020.
ista: Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection
graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917.
mla: Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane
Convex Sets.” Discrete and Computational Geometry, vol. 63, no. 4, Springer
Nature, 2020, pp. 888–917, doi:10.1007/s00454-020-00213-z.
short: J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020)
888–917.
date_created: 2020-06-14T22:00:51Z
date_published: 2020-06-05T00:00:00Z
date_updated: 2023-08-21T08:49:18Z
day: '05'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00213-z
external_id:
arxiv:
- '1803.06710'
isi:
- '000538229000001'
intvolume: ' 63'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.06710
month: '06'
oa: 1
oa_version: Preprint
page: 888-917
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Almost all string graphs are intersection graphs of plane convex sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 63
year: '2020'
...
---
_id: '8163'
abstract:
- lang: eng
text: Fejes Tóth [3] studied approximations of smooth surfaces in three-space by
piecewise flat triangular meshes with a given number of vertices on the surface
that are optimal with respect to Hausdorff distance. He proves that this Hausdorff
distance decreases inversely proportional with the number of vertices of the approximating
mesh if the surface is convex. He also claims that this Hausdorff distance is
inversely proportional to the square of the number of vertices for a specific
non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by
two congruent circles. We refute this claim, and show that the asymptotic behavior
of the Hausdorff distance is linear, that is the same as for convex surfaces.
acknowledgement: "The authors are greatly indebted to Dror Atariah, Günther Rote and
John Sullivan for discussion and suggestions. The authors also thank Jean-Daniel
Boissonnat, Ramsay Dyer, David de Laat and Rien van de Weijgaert for discussion.
This work has been supported in part by the European Union’s Seventh Framework Programme
for Research of the\r\nEuropean Commission, under FET-Open grant number 255827 (CGL
Computational Geometry Learning) and ERC Grant Agreement number 339025 GUDHI (Algorithmic
Foundations of Geometry Understanding in Higher Dimensions), the European Union’s
Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie
grant agreement number 754411,and the Austrian Science Fund (FWF): Z00342 N31."
article_processing_charge: No
article_type: original
author:
- first_name: Gert
full_name: Vegter, Gert
last_name: Vegter
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Vegter G, Wintraecken M. Refutation of a claim made by Fejes Tóth on the accuracy
of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 2020;57(2):193-199.
doi:10.1556/012.2020.57.2.1454
apa: Vegter, G., & Wintraecken, M. (2020). Refutation of a claim made by Fejes
Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica.
Akadémiai Kiadó. https://doi.org/10.1556/012.2020.57.2.1454
chicago: Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes
Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum
Hungarica. Akadémiai Kiadó, 2020. https://doi.org/10.1556/012.2020.57.2.1454.
ieee: G. Vegter and M. Wintraecken, “Refutation of a claim made by Fejes Tóth on
the accuracy of surface meshes,” Studia Scientiarum Mathematicarum Hungarica,
vol. 57, no. 2. Akadémiai Kiadó, pp. 193–199, 2020.
ista: Vegter G, Wintraecken M. 2020. Refutation of a claim made by Fejes Tóth on
the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 57(2),
193–199.
mla: Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes
Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum
Hungarica, vol. 57, no. 2, Akadémiai Kiadó, 2020, pp. 193–99, doi:10.1556/012.2020.57.2.1454.
short: G. Vegter, M. Wintraecken, Studia Scientiarum Mathematicarum Hungarica 57
(2020) 193–199.
date_created: 2020-07-24T07:09:18Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2023-10-10T13:05:27Z
day: '24'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1556/012.2020.57.2.1454
ec_funded: 1
external_id:
isi:
- '000570978400005'
file:
- access_level: open_access
content_type: application/pdf
creator: mwintrae
date_created: 2020-07-24T07:09:06Z
date_updated: 2020-07-24T07:09:06Z
file_id: '8164'
file_name: 57-2-05_4214-1454Vegter-Wintraecken_OpenAccess_CC-BY-NC.pdf
file_size: 1476072
relation: main_file
file_date_updated: 2020-07-24T07:09:06Z
has_accepted_license: '1'
intvolume: ' 57'
isi: 1
issue: '2'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 193-199
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: Studia Scientiarum Mathematicarum Hungarica
publication_identifier:
eissn:
- 1588-2896
issn:
- 0081-6906
publication_status: published
publisher: Akadémiai Kiadó
quality_controlled: '1'
scopus_import: '1'
status: public
title: Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2020'
...
---
_id: '9299'
abstract:
- lang: eng
text: We call a multigraph non-homotopic if it can be drawn in the plane in such
a way that no two edges connecting the same pair of vertices can be continuously
transformed into each other without passing through a vertex, and no loop can
be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic
multigraph on n>1 vertices can have arbitrarily many edges. We prove that the
number of crossings between the edges of a non-homotopic multigraph with n vertices
and m>4n edges is larger than cm2n for some constant c>0 , and that this
bound is tight up to a polylogarithmic factor. We also show that the lower bound
is not asymptotically sharp as n is fixed and m⟶∞ .
acknowledgement: Supported by the National Research, Development and Innovation Office,
NKFIH, KKP-133864, K-131529, K-116769, K-132696, by the Higher Educational Institutional
Excellence Program 2019 NKFIH-1158-6/2019, the Austrian Science Fund (FWF), grant
Z 342-N31, by the Ministry of Education and Science of the Russian Federation MegaGrant
No. 075-15-2019-1926, and by the ERC Synergy Grant “Dynasnet” No. 810115. A full
version can be found at https://arxiv.org/abs/2006.14908.
article_processing_charge: No
arxiv: 1
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Gábor
full_name: Tardos, Gábor
last_name: Tardos
- first_name: Géza
full_name: Tóth, Géza
last_name: Tóth
citation:
ama: 'Pach J, Tardos G, Tóth G. Crossings between non-homotopic edges. In: 28th
International Symposium on Graph Drawing and Network Visualization. Vol 12590.
LNCS. Springer Nature; 2020:359-371. doi:10.1007/978-3-030-68766-3_28'
apa: 'Pach, J., Tardos, G., & Tóth, G. (2020). Crossings between non-homotopic
edges. In 28th International Symposium on Graph Drawing and Network Visualization
(Vol. 12590, pp. 359–371). Virtual, Online: Springer Nature. https://doi.org/10.1007/978-3-030-68766-3_28'
chicago: Pach, János, Gábor Tardos, and Géza Tóth. “Crossings between Non-Homotopic
Edges.” In 28th International Symposium on Graph Drawing and Network Visualization,
12590:359–71. LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-68766-3_28.
ieee: J. Pach, G. Tardos, and G. Tóth, “Crossings between non-homotopic edges,”
in 28th International Symposium on Graph Drawing and Network Visualization,
Virtual, Online, 2020, vol. 12590, pp. 359–371.
ista: 'Pach J, Tardos G, Tóth G. 2020. Crossings between non-homotopic edges. 28th
International Symposium on Graph Drawing and Network Visualization. GD: Graph
Drawing and Network VisualizationLNCS vol. 12590, 359–371.'
mla: Pach, János, et al. “Crossings between Non-Homotopic Edges.” 28th International
Symposium on Graph Drawing and Network Visualization, vol. 12590, Springer
Nature, 2020, pp. 359–71, doi:10.1007/978-3-030-68766-3_28.
short: J. Pach, G. Tardos, G. Tóth, in:, 28th International Symposium on Graph Drawing
and Network Visualization, Springer Nature, 2020, pp. 359–371.
conference:
end_date: 2020-09-18
location: Virtual, Online
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2020-09-16
date_created: 2021-03-28T22:01:44Z
date_published: 2020-09-20T00:00:00Z
date_updated: 2021-04-06T11:32:32Z
day: '20'
department:
- _id: HeEd
doi: 10.1007/978-3-030-68766-3_28
external_id:
arxiv:
- '2006.14908'
intvolume: ' 12590'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2006.14908
month: '09'
oa: 1
oa_version: Preprint
page: 359-371
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: 28th International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030687656'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Crossings between non-homotopic edges
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12590
year: '2020'
...