---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '20293'
abstract:
- lang: eng
text: Motivated by questions arising at the intersection of information theory and
geometry, we compare two dissimilarity measures between finite categorical distributions.
One is the well-known Jensen–Shannon divergence, which is easy to compute and
whose square root is a proper metric. The other is what we call the minmax divergence,
which is harder to compute. Just like the Jensen–Shannon divergence, it arises
naturally from the Kullback–Leibler divergence. The main contribution of this
paper is a proof showing that the minmax divergence can be tightly approximated
by the Jensen–Shannon divergence. The bounds suggest that the square root of the
minmax divergence is a metric, and we prove that this is indeed true in the one-dimensional
case. The general case remains open. Finally, we consider analogous questions
in the context of another Bregman divergence and the corresponding Burbea–Rao
(Jensen–Bregman) divergence.
acknowledgement: "This research received partial funding from the European Research
Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation
programme, grant no. 788183, the\r\nWittgenstein Prize, Austrian Science Fund (FWF),
grant no. Z 342-N31, the DFG Collaborative\r\nResearch Center TRR 109, ‘Discretization
in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35, and
the 2022 Google Research Scholar Award for project ‘Algorithms for Topological Analysis
of Neural Networks’. The APC was waived."
article_number: '854'
article_processing_charge: Yes
article_type: original
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: Ziga
full_name: Virk, Ziga
id: 2E36B656-F248-11E8-B48F-1D18A9856A87
last_name: Virk
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: Akopyan A, Edelsbrunner H, Virk Z, Wagner H. Tight bounds between the Jensen–Shannon
divergence and the minmax divergence. Entropy. 2025;27(8). doi:10.3390/e27080854
apa: Akopyan, A., Edelsbrunner, H., Virk, Z., & Wagner, H. (2025). Tight bounds
between the Jensen–Shannon divergence and the minmax divergence. Entropy.
MDPI. https://doi.org/10.3390/e27080854
chicago: Akopyan, Arseniy, Herbert Edelsbrunner, Ziga Virk, and Hubert Wagner. “Tight
Bounds between the Jensen–Shannon Divergence and the Minmax Divergence.” Entropy.
MDPI, 2025. https://doi.org/10.3390/e27080854.
ieee: A. Akopyan, H. Edelsbrunner, Z. Virk, and H. Wagner, “Tight bounds between
the Jensen–Shannon divergence and the minmax divergence,” Entropy, vol.
27, no. 8. MDPI, 2025.
ista: Akopyan A, Edelsbrunner H, Virk Z, Wagner H. 2025. Tight bounds between the
Jensen–Shannon divergence and the minmax divergence. Entropy. 27(8), 854.
mla: Akopyan, Arseniy, et al. “Tight Bounds between the Jensen–Shannon Divergence
and the Minmax Divergence.” Entropy, vol. 27, no. 8, 854, MDPI, 2025, doi:10.3390/e27080854.
short: A. Akopyan, H. Edelsbrunner, Z. Virk, H. Wagner, Entropy 27 (2025).
corr_author: '1'
date_created: 2025-09-07T22:01:33Z
date_published: 2025-08-01T00:00:00Z
date_updated: 2025-09-30T14:32:31Z
day: '01'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.3390/e27080854
ec_funded: 1
external_id:
isi:
- '001557476000001'
pmid:
- '40870326'
file:
- access_level: open_access
checksum: 65c5399c4015d9c8abb8c7a96f3d7836
content_type: application/pdf
creator: dernst
date_created: 2025-09-08T07:55:48Z
date_updated: 2025-09-08T07:55:48Z
file_id: '20309'
file_name: 2025_Entropy_Akopyan.pdf
file_size: 379340
relation: main_file
success: 1
file_date_updated: 2025-09-08T07:55:48Z
has_accepted_license: '1'
intvolume: ' 27'
isi: 1
issue: '8'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
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: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Entropy
publication_identifier:
eissn:
- 1099-4300
publication_status: published
publisher: MDPI
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds between the Jensen–Shannon divergence and the minmax divergence
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 27
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20323'
abstract:
- lang: eng
text: We establish several results combining discrete Morse theory and microlocal
sheaf theory in the setting of finite posets and simplicial complexes. Our primary
tool is a computationally tractable description of the bounded derived category
of sheaves on a poset with the Alexandrov topology. We prove that each bounded
complex of sheaves on a finite poset admits a unique (up to isomorphism of complexes)
minimal injective resolution, and we provide algorithms for computing minimal
injective resolution of an injective complex, as well as several useful functors
between derived categories of sheaves. For the constant sheaf on a simplicial
complex, we give asymptotically tight bounds on the complexity of computing the
minimal injective resolution using those algorithms. Our main result is a novel
definition of the discrete microsupport of a bounded complex of sheaves on a finite
poset. We detail several foundational properties of the discrete microsupport,
as well as a microlocal generalization of the discrete homological Morse theorem
and Morse inequalities.
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. Z342-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_number: '108068'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Adam
full_name: Brown, Adam
id: 70B7FDF6-608D-11E9-9333-8535E6697425
last_name: Brown
- first_name: Ondrej
full_name: Draganov, Ondrej
id: 2B23F01E-F248-11E8-B48F-1D18A9856A87
last_name: Draganov
orcid: 0000-0003-0464-3823
citation:
ama: Brown A, Draganov O. Discrete microlocal Morse theory. Journal of Pure and
Applied Algebra. 2025;229(10). doi:10.1016/j.jpaa.2025.108068
apa: Brown, A., & Draganov, O. (2025). Discrete microlocal Morse theory. Journal
of Pure and Applied Algebra. Elsevier. https://doi.org/10.1016/j.jpaa.2025.108068
chicago: Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” Journal
of Pure and Applied Algebra. Elsevier, 2025. https://doi.org/10.1016/j.jpaa.2025.108068.
ieee: A. Brown and O. Draganov, “Discrete microlocal Morse theory,” Journal of
Pure and Applied Algebra, vol. 229, no. 10. Elsevier, 2025.
ista: Brown A, Draganov O. 2025. Discrete microlocal Morse theory. Journal of Pure
and Applied Algebra. 229(10), 108068.
mla: Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” Journal
of Pure and Applied Algebra, vol. 229, no. 10, 108068, Elsevier, 2025, doi:10.1016/j.jpaa.2025.108068.
short: A. Brown, O. Draganov, Journal of Pure and Applied Algebra 229 (2025).
corr_author: '1'
date_created: 2025-09-10T05:40:09Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-12-30T07:55:21Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jpaa.2025.108068
ec_funded: 1
external_id:
arxiv:
- '2209.14993'
file:
- access_level: open_access
checksum: 39bcad462278c9322ef810af7db67f56
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T07:55:08Z
date_updated: 2025-12-30T07:55:08Z
file_id: '20886'
file_name: 2025_JourPureAppliedAlgebra_Brown.pdf
file_size: 3090836
relation: main_file
success: 1
file_date_updated: 2025-12-30T07:55:08Z
has_accepted_license: '1'
intvolume: ' 229'
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Journal of Pure and Applied Algebra
publication_identifier:
issn:
- 0022-4049
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '18981'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Discrete microlocal 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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 229
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20658'
abstract:
- lang: eng
text: The medial axis of a smoothly embedded surface in R^3 consists of all points
for which the Euclidean distance function on the surface has at least two global
minima. We generalize this notion to the mid-sphere axis, which consists of all
points for which the Euclidean distance function has two interchanging saddles
that swap their partners in the pairing by persistent homology. It offers a discrete-algebraic
multi-scale approach to computing ridge-like structures on the surface. As a proof
of concept, an algorithm that computes stair-case approximations of the mid-sphere
axis is provided.
alternative_title:
- LNCS
article_processing_charge: No
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: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Martin H
full_name: Thoresen, Martin H
id: 47CB1472-F248-11E8-B48F-1D18A9856A87
last_name: Thoresen
citation:
ama: 'Edelsbrunner H, Stephenson ER, Thoresen MH. The mid-sphere cousin of the medial
axis transform. In: 4th International Joint Conference on Discrete Geometry
and Mathematical Morphology. Vol 16296. Springer Nature; 2025:133-147. doi:10.1007/978-3-032-09544-2_10'
apa: 'Edelsbrunner, H., Stephenson, E. R., & Thoresen, M. H. (2025). The mid-sphere
cousin of the medial axis transform. In 4th International Joint Conference
on Discrete Geometry and Mathematical Morphology (Vol. 16296, pp. 133–147).
Groningen, The Netherlands: Springer Nature. https://doi.org/10.1007/978-3-032-09544-2_10'
chicago: Edelsbrunner, Herbert, Elizabeth R Stephenson, and Martin H Thoresen. “The
Mid-Sphere Cousin of the Medial Axis Transform.” In 4th International Joint
Conference on Discrete Geometry and Mathematical Morphology, 16296:133–47.
Springer Nature, 2025. https://doi.org/10.1007/978-3-032-09544-2_10.
ieee: H. Edelsbrunner, E. R. Stephenson, and M. H. Thoresen, “The mid-sphere cousin
of the medial axis transform,” in 4th International Joint Conference on Discrete
Geometry and Mathematical Morphology, Groningen, The Netherlands, 2025, vol.
16296, pp. 133–147.
ista: 'Edelsbrunner H, Stephenson ER, Thoresen MH. 2025. The mid-sphere cousin of the medial
axis transform. 4th International Joint Conference on Discrete Geometry and Mathematical
Morphology. DGMM: Discrete Geometry and Mathematical Morphology, LNCS, vol. 16296,
133–147.'
mla: Edelsbrunner, Herbert, et al. “The Mid-Sphere Cousin of the Medial Axis Transform.”
4th International Joint Conference on Discrete Geometry and Mathematical Morphology,
vol. 16296, Springer Nature, 2025, pp. 133–47, doi:10.1007/978-3-032-09544-2_10.
short: H. Edelsbrunner, E.R. Stephenson, M.H. Thoresen, in:, 4th International Joint
Conference on Discrete Geometry and Mathematical Morphology, Springer Nature,
2025, pp. 133–147.
conference:
end_date: 2025-11-06
location: Groningen, The Netherlands
name: 'DGMM: Discrete Geometry and Mathematical Morphology'
start_date: 2025-11-03
date_created: 2025-11-23T23:01:37Z
date_published: 2025-11-01T00:00:00Z
date_updated: 2025-11-24T10:05:11Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-032-09544-2_10
external_id:
arxiv:
- '2504.14743'
intvolume: ' 16296'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2504.14743
month: '11'
oa: 1
oa_version: Preprint
page: 133-147
publication: 4th International Joint Conference on Discrete Geometry and Mathematical
Morphology
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032095435'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The mid-sphere cousin of the medial axis transform
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16296
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20729'
abstract:
- lang: eng
text: 'Persistence modules (defined as a sequence of vector spaces and linear maps
between them) are a key tool in topological data analysis. They are easy to interpret
and fast to compute. However, when considering persistence maps (i.e. maps between
persistence modules), these properties are lost. We propose a new invariant for
persistence maps consisting of a partial matching such that: it is easy to interpret,
it is more discriminative than the image of the persistence map, and can be calculated
with cubical complexity.'
acknowledgement: Álvaro Torras-Casas contract is funded by the French Agence Nationale
de la Recherche through the project reference ANR-22-CPJ1-0047-01. Rocio Gonzalez-Diaz
is partially funded by the European Union under grant agreement no. 101070028-2
(REXASI-PRO).
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Rocio
full_name: Gonzalez-Diaz, Rocio
last_name: Gonzalez-Diaz
- first_name: Manuel
full_name: Soriano Trigueros, Manuel
id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8
last_name: Soriano Trigueros
orcid: 0000-0003-2449-1433
- first_name: Alvaro
full_name: Torras-Casas, Alvaro
last_name: Torras-Casas
citation:
ama: 'Gonzalez-Diaz R, Soriano Trigueros M, Torras-Casas A. Additive partial matchings
for persistent homology. In: Proceedings of the 2025 International Symposium
on Symbolic and Algebraic Computation. Association for Computing Machinery;
2025:188-196. doi:10.1145/3747199.3747561'
apa: 'Gonzalez-Diaz, R., Soriano Trigueros, M., & Torras-Casas, A. (2025). Additive
partial matchings for persistent homology. In Proceedings of the 2025 International
Symposium on Symbolic and Algebraic Computation (pp. 188–196). Guanajuato,
Mexico: Association for Computing Machinery. https://doi.org/10.1145/3747199.3747561'
chicago: Gonzalez-Diaz, Rocio, Manuel Soriano Trigueros, and Alvaro Torras-Casas.
“Additive Partial Matchings for Persistent Homology.” In Proceedings of the
2025 International Symposium on Symbolic and Algebraic Computation, 188–96.
Association for Computing Machinery, 2025. https://doi.org/10.1145/3747199.3747561.
ieee: R. Gonzalez-Diaz, M. Soriano Trigueros, and A. Torras-Casas, “Additive partial
matchings for persistent homology,” in Proceedings of the 2025 International
Symposium on Symbolic and Algebraic Computation, Guanajuato, Mexico, 2025,
pp. 188–196.
ista: 'Gonzalez-Diaz R, Soriano Trigueros M, Torras-Casas A. 2025. Additive partial
matchings for persistent homology. Proceedings of the 2025 International Symposium
on Symbolic and Algebraic Computation. ISSAC: International Symposium on Symbolic
and Algebraic Computation, 188–196.'
mla: Gonzalez-Diaz, Rocio, et al. “Additive Partial Matchings for Persistent Homology.”
Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation,
Association for Computing Machinery, 2025, pp. 188–96, doi:10.1145/3747199.3747561.
short: R. Gonzalez-Diaz, M. Soriano Trigueros, A. Torras-Casas, in:, Proceedings
of the 2025 International Symposium on Symbolic and Algebraic Computation, Association
for Computing Machinery, 2025, pp. 188–196.
conference:
end_date: 2025-08-01
location: Guanajuato, Mexico
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2025-07-28
corr_author: '1'
date_created: 2025-12-07T23:02:01Z
date_published: 2025-11-10T00:00:00Z
date_updated: 2025-12-09T13:46:42Z
day: '10'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1145/3747199.3747561
file:
- access_level: open_access
checksum: 1c299cca165a20e2518afe4fda63dbf1
content_type: application/pdf
creator: dernst
date_created: 2025-12-09T13:43:17Z
date_updated: 2025-12-09T13:43:17Z
file_id: '20751'
file_name: 2025_ISSAC_GonzalezDiaz.pdf
file_size: 761617
relation: main_file
success: 1
file_date_updated: 2025-12-09T13:43:17Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 188-196
publication: Proceedings of the 2025 International Symposium on Symbolic and Algebraic
Computation
publication_identifier:
isbn:
- '9798400720758'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Additive partial matchings for persistent homology
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
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21016'
abstract:
- lang: eng
text: Motivated by applications in chemistry, we give a homlogical definition of
tunnels, or more generally cobordisms, connecting disjoint parts of a cell complex.
For a filtered complex, this defines a persistence module. We give a method for
identifying birth and death times using kernel persistence and a matrix reduction
algorithm for pairing birth and death times.
acknowledgement: "Y. B. B. and L. F. were funded by the Independent Research Fund
Denmark, grant\r\nnumber 1026-00037. T. H. was partially supported by the European
Research Council\r\n(ERC) Horizon 2020, grant number 788183."
article_number: '2505.17858'
article_processing_charge: No
arxiv: 1
author:
- first_name: Yossi
full_name: Bleile, Yossi
id: 920a7385-7995-11ef-9bfd-8c434cd8f3c2
last_name: Bleile
orcid: 0000-0002-4861-9174
- first_name: Lisbeth
full_name: Fajstrup, Lisbeth
last_name: Fajstrup
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Anne Marie
full_name: Svane, Anne Marie
last_name: Svane
- first_name: Søren Strandskov
full_name: Sørensen, Søren Strandskov
last_name: Sørensen
citation:
ama: Bokor Bleile Y, Fajstrup L, Heiss T, Svane AM, Sørensen SS. Identifying cobordisms
using kernel persistence. arXiv. doi:10.48550/arXiv.2505.17858
apa: Bokor Bleile, Y., Fajstrup, L., Heiss, T., Svane, A. M., & Sørensen, S.
S. (n.d.). Identifying cobordisms using kernel persistence. arXiv. https://doi.org/10.48550/arXiv.2505.17858
chicago: Bokor Bleile, Yossi, Lisbeth Fajstrup, Teresa Heiss, Anne Marie Svane,
and Søren Strandskov Sørensen. “Identifying Cobordisms Using Kernel Persistence.”
ArXiv, n.d. https://doi.org/10.48550/arXiv.2505.17858.
ieee: Y. Bokor Bleile, L. Fajstrup, T. Heiss, A. M. Svane, and S. S. Sørensen, “Identifying
cobordisms using kernel persistence,” arXiv. .
ista: Bokor Bleile Y, Fajstrup L, Heiss T, Svane AM, Sørensen SS. Identifying cobordisms
using kernel persistence. arXiv, 2505.17858.
mla: Bokor Bleile, Yossi, et al. “Identifying Cobordisms Using Kernel Persistence.”
ArXiv, 2505.17858, doi:10.48550/arXiv.2505.17858.
short: Y. Bokor Bleile, L. Fajstrup, T. Heiss, A.M. Svane, S.S. Sørensen, ArXiv
(n.d.).
das_tickbox: '1'
date_created: 2026-01-20T10:12:21Z
date_published: 2025-05-23T00:00:00Z
date_updated: 2026-07-22T06:33:07Z
day: '23'
department:
- _id: HeEd
doi: 10.48550/arXiv.2505.17858
ec_funded: 1
external_id:
arxiv:
- '2505.17858'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.17858
month: '05'
oa: 1
oa_version: Preprint
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
publication: arXiv
publication_status: submitted
status: public
title: Identifying cobordisms using kernel persistence
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21050'
abstract:
- lang: eng
text: "In 1873, James C. Maxwell conjectured that the electric field generated by
$n$ point charges in generic position has at most $(n-1)^2$ isolated zeroes. The
first (non-optimal) upper bound was only obtained in 2007 by Gabrielov, Novikov
and Shapiro, who also posed two additional interesting conjectures.\r\n In this
article, we give the best upper bound known to date on the number of zeroes of
the electric field, and construct a counterexample to a conjecture of Gabrielov,
Novikov and Shapiro that the number of equilibria cannot exceed those of the distance
function defined by the unit point charges.\r\n Finally, we note that it is quite
possible that Maxwell's quadratic upper bound is not tight, so it is prudent to
find smaller bounds. Hence, we also explore examples and construct configurations
of charges achieving the highest ratios of the number of electric field zeroes
by point charges found to this day."
article_number: '2501.05315'
article_processing_charge: No
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: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Gonçalo
full_name: Olivera, Gonçalo
last_name: Olivera
citation:
ama: Edelsbrunner H, Fillmore CD, Olivera G. Counting equilibria of the electrostatic
potential. arXiv. doi:10.48550/ARXIV.2501.05315
apa: Edelsbrunner, H., Fillmore, C. D., & Olivera, G. (n.d.). Counting equilibria
of the electrostatic potential. arXiv. https://doi.org/10.48550/ARXIV.2501.05315
chicago: Edelsbrunner, Herbert, Christopher D Fillmore, and Gonçalo Olivera. “Counting
Equilibria of the Electrostatic Potential.” ArXiv, n.d. https://doi.org/10.48550/ARXIV.2501.05315.
ieee: H. Edelsbrunner, C. D. Fillmore, and G. Olivera, “Counting equilibria of the
electrostatic potential,” arXiv. .
ista: Edelsbrunner H, Fillmore CD, Olivera G. Counting equilibria of the electrostatic
potential. arXiv, 2501.05315.
mla: Edelsbrunner, Herbert, et al. “Counting Equilibria of the Electrostatic Potential.”
ArXiv, 2501.05315, doi:10.48550/ARXIV.2501.05315.
short: H. Edelsbrunner, C.D. Fillmore, G. Olivera, ArXiv (n.d.).
corr_author: '1'
das_tickbox: '1'
date_created: 2026-01-27T14:29:27Z
date_published: 2025-03-20T00:00:00Z
date_updated: 2026-07-22T06:33:55Z
day: '20'
department:
- _id: HeEd
doi: 10.48550/ARXIV.2501.05315
external_id:
arxiv:
- '2501.05315'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2501.05315
month: '03'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
record:
- id: '21021'
relation: dissertation_contains
status: public
- id: '21931'
relation: later_version
status: public
status: public
title: Counting equilibria of the electrostatic potential
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_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.
2024;8:1101-1119. doi:10.1007/s41468-023-00126-9
apa: Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M.
(2024). 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, 2024. 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, vol. 8. Springer Nature, pp. 1101–1119, 2024.
ista: Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2024. Geometric
characterization of the persistence of 1D maps. Journal of Applied and Computational
Topology. 8, 1101–1119.
mla: Biswas, Ranita, et al. “Geometric Characterization of the Persistence of 1D
Maps.” Journal of Applied and Computational Topology, vol. 8, Springer
Nature, 2024, pp. 1101–19, doi:10.1007/s41468-023-00126-9.
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal
of Applied and Computational Topology 8 (2024) 1101–1119.
corr_author: '1'
date_created: 2023-07-02T22:00:44Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-04-07T12:58:47Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s41468-023-00126-9
ec_funded: 1
external_id:
pmid:
- '39678706'
file:
- access_level: open_access
checksum: d493df5088c222b88d9ca46b623ad0ee
content_type: application/pdf
creator: dernst
date_created: 2025-01-09T07:39:41Z
date_updated: 2025-01-09T07:39:41Z
file_id: '18783'
file_name: 2024_JourApplCompTopo_Biswas.pdf
file_size: 476896
relation: main_file
success: 1
file_date_updated: 2025-01-09T07:39:41Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 1101-1119
pmid: 1
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Persistent Homology, Algorithms and Stochastic Geometry
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '15094'
relation: dissertation_contains
status: public
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
volume: 8
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. 2024;72:29-48. doi:10.1007/s00454-023-00566-1
apa: Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2024).
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,
2024. 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, vol. 72. Springer Nature, pp. 29–48, 2024.
ista: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2024. On angles
in higher order Brillouin tessellations and related tilings in the plane. Discrete
and Computational Geometry. 72, 29–48.
mla: Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations
and Related Tilings in the Plane.” Discrete and Computational Geometry,
vol. 72, Springer Nature, 2024, pp. 29–48, doi:10.1007/s00454-023-00566-1.
short: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete
and Computational Geometry 72 (2024) 29–48.
corr_author: '1'
date_created: 2023-09-17T22:01:10Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2025-04-23T08:41:59Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-023-00566-1
ec_funded: 1
external_id:
arxiv:
- '2204.01076'
isi:
- '001060727600004'
pmid:
- '39610762'
file:
- access_level: open_access
checksum: b207b4e00f904e8ea8a30e24f0251f79
content_type: application/pdf
creator: dernst
date_created: 2024-07-22T09:43:19Z
date_updated: 2024-07-22T09:43:19Z
file_id: '17301'
file_name: 2024_DiscreteComputGeom_Edelsbrunner.pdf
file_size: 892019
relation: main_file
success: 1
file_date_updated: 2024-07-22T09:43:19Z
has_accepted_license: '1'
intvolume: ' 72'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 29-48
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: Mathematics, Computer Science
- _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'
scopus_import: '1'
status: public
title: On angles in higher order Brillouin tessellations and related tilings in the
plane
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: 72
year: '2024'
...
---
_id: '14888'
abstract:
- lang: eng
text: 'A face in a curve arrangement is called popular if it is bounded by the same
curve multiple times. Motivated by the automatic generation of curved nonogram
puzzles, we investigate possibilities to eliminate the popular faces in an arrangement
by inserting a single additional curve. This turns out to be NP-hard; however,
it becomes tractable when the number of popular faces is small: We present a probabilistic
FPT-approach in the number of popular faces.'
acknowledgement: 'This work was initiated at the 16th European Research Week on Geometric
Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF):
W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035].
A preliminary version of this work has been presented at the 38th European Workshop
on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper,
which includes appendices but is otherwise identical, is available as a technical
report [10].'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Phoebe
full_name: De Nooijer, Phoebe
last_name: De Nooijer
- first_name: Soeren
full_name: Terziadis, Soeren
last_name: Terziadis
- first_name: Alexandra
full_name: Weinberger, Alexandra
last_name: Weinberger
- 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: Tamara
full_name: Mchedlidze, Tamara
last_name: Mchedlidze
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
citation:
ama: 'De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve
arrangements. In: 31st International Symposium on Graph Drawing and Network
Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2'
apa: 'De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T.,
Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements.
In 31st International Symposium on Graph Drawing and Network Visualization
(Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature.
https://doi.org/10.1007/978-3-031-49275-4_2'
chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová,
Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve
Arrangements.” In 31st International Symposium on Graph Drawing and Network
Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2.
ieee: P. De Nooijer et al., “Removing popular faces in curve arrangements,”
in 31st International Symposium on Graph Drawing and Network Visualization,
Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.
ista: 'De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler
M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International
Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network
Visualization, LNCS, vol. 14466, 18–33.'
mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.”
31st International Symposium on Graph Drawing and Network Visualization,
vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2.
short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M.
Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network
Visualization, Springer Nature, 2024, pp. 18–33.
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-01-28T23:01:43Z
date_published: 2024-01-06T00:00:00Z
date_updated: 2025-09-04T11:52:35Z
day: '06'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/978-3-031-49275-4_2
external_id:
arxiv:
- '2202.12175'
isi:
- '001207942000002'
intvolume: ' 14466'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2202.12175
month: '01'
oa: 1
oa_version: Preprint
page: 18-33
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031492747'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Removing popular faces in curve arrangements
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14466
year: '2024'
...
---
_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: 2026-04-16T09:12:37Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-031-49272-3_23
ec_funded: 1
external_id:
arxiv:
- '2306.13201'
isi:
- '001207939600023'
intvolume: ' 14465'
isi: 1
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: Mathematics, Computer Science
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eisbn:
- '9783031492723'
eissn:
- 1611-3349
isbn:
- '9783031492716'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21253'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Decomposition of geometric graphs into star-forests
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 14465
year: '2024'
...
---
_id: '15093'
abstract:
- lang: eng
text: We present a dynamic data structure for maintaining the persistent homology
of a time series of real numbers. The data structure supports local operations,
including the insertion and deletion of an item and the cutting and concatenating
of lists, each in time O(log n + k), in which n counts the critical items and
k the changes in the augmented persistence diagram. To achieve this, we design
a tailor-made tree structure with an unconventional representation, referred to
as banana tree, which may be useful in its own right.
acknowledgement: The first and second authors are funded by the European Research Council under the
European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha
Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31,
and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The
third author received funding by the European Research Council under the European
Union’s Horizon 2020research and innovation programme, ERC grant no. 101019564, “The Design of Modern Fully Dynamic DataStructures
(MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize
with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant
no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. The
fourth author is funded by the Vienna Graduate School on Computational Optimization,
FWF project no. W1260-N35.
article_processing_charge: No
arxiv: 1
author:
- 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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Lara
full_name: Ost, Lara
last_name: Ost
citation:
ama: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. Dynamically maintaining
the persistent homology of time series. In: Woodruff DP, ed. Proceedings of
the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society
for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11'
apa: 'Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M., & Ost, L.
(2024). Dynamically maintaining the persistent homology of time series. In D.
P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.11'
chicago: Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika Henzinger,
and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.”
In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied
Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
ieee: S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, and L. Ost, “Dynamically
maintaining the persistent homology of time series,” in Proceedings of the
2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria,
VA, USA, 2024, pp. 243–295.
ista: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically
maintaining the persistent homology of time series. Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete
Algorithms, 243–295.'
mla: Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent
Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial
and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11.
short: S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P.
Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
conference:
end_date: 2024-01-10
location: Alexandria, VA, USA
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2024-01-07
corr_author: '1'
date_created: 2024-03-08T10:27:39Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2026-04-07T12:58:47Z
day: '04'
department:
- _id: HeEd
- _id: MoHe
doi: 10.1137/1.9781611977912.11
ec_funded: 1
editor:
- first_name: David P.
full_name: Woodruff, David P.
last_name: Woodruff
external_id:
arxiv:
- '2311.01115'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2311.01115
month: '01'
oa: 1
oa_version: Preprint
page: 243 - 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: Mathematics, Computer Science
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA)
publication_identifier:
eisbn:
- '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '15094'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Dynamically maintaining the persistent homology of time series
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
OA_place: publisher
_id: '15094'
abstract:
- lang: eng
text: "Point sets, geometric networks, and arrangements of hyperplanes are fundamental
objects in\r\ndiscrete geometry that have captivated mathematicians for centuries,
if not millennia. This\r\nthesis seeks to cast new light on these structures by
illustrating specific instances where a\r\ntopological perspective, specifically
through discrete Morse theory and persistent homology,\r\nprovides valuable insights.\r\n\r\nAt
first glance, the topology of these geometric objects might seem uneventful: point
sets\r\nessentially lack of topology, arrangements of hyperplanes are a decomposition
of Rd, which\r\nis a contractible space, and the topology of a network primarily
involves the enumeration\r\nof connected components and cycles within the network.
However, beneath this apparent\r\nsimplicity, there lies an array of intriguing
structures, a small subset of which will be uncovered\r\nin this thesis.\r\n\r\nFocused
on three case studies, each addressing one of the mentioned objects, this work\r\nwill
showcase connections that intertwine topology with diverse fields such as combinatorial\r\ngeometry,
algorithms and data structures, and emerging applications like spatial biology.\r\n\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- 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
citation:
ama: Cultrera di Montesano S. Persistence and Morse theory for discrete geometric
structures. 2024. doi:10.15479/at:ista:15094
apa: Cultrera di Montesano, S. (2024). Persistence and Morse theory for discrete
geometric structures. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:15094
chicago: Cultrera di Montesano, Sebastiano. “Persistence and Morse Theory for Discrete
Geometric Structures.” Institute of Science and Technology Austria, 2024. https://doi.org/10.15479/at:ista:15094.
ieee: S. Cultrera di Montesano, “Persistence and Morse theory for discrete geometric
structures,” Institute of Science and Technology Austria, 2024.
ista: Cultrera di Montesano S. 2024. Persistence and Morse theory for discrete geometric
structures. Institute of Science and Technology Austria.
mla: Cultrera di Montesano, Sebastiano. Persistence and Morse Theory for Discrete
Geometric Structures. Institute of Science and Technology Austria, 2024, doi:10.15479/at:ista:15094.
short: S. Cultrera di Montesano, Persistence and Morse Theory for Discrete Geometric
Structures, Institute of Science and Technology Austria, 2024.
corr_author: '1'
date_created: 2024-03-08T15:28:10Z
date_published: 2024-03-08T00:00:00Z
date_updated: 2026-04-07T12:58:48Z
day: '08'
ddc:
- '514'
- '500'
- '516'
degree_awarded: PhD
department:
- _id: GradSch
- _id: HeEd
doi: 10.15479/at:ista:15094
ec_funded: 1
file:
- access_level: open_access
checksum: 1e468bfa42a7dcf04d89f4dadc621c87
content_type: application/pdf
creator: scultrer
date_created: 2024-03-14T08:55:07Z
date_updated: 2024-03-14T08:55:07Z
file_id: '15112'
file_name: Thesis Sebastiano.pdf
file_size: 4106872
relation: main_file
success: 1
- access_level: closed
checksum: bcbd213490f5a7e68855a092bbce93f1
content_type: application/zip
creator: scultrer
date_created: 2024-03-14T08:56:24Z
date_updated: 2024-03-14T14:14:35Z
file_id: '15113'
file_name: Thesis (1).zip
file_size: 4746234
relation: source_file
file_date_updated: 2024-03-14T14:14:35Z
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '108'
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Persistent Homology, Algorithms and Stochastic Geometry
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '15091'
relation: part_of_dissertation
status: public
- id: '11660'
relation: part_of_dissertation
status: public
- id: '15090'
relation: part_of_dissertation
status: public
- id: '15093'
relation: part_of_dissertation
status: public
- id: '13182'
relation: part_of_dissertation
status: public
- id: '11658'
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: Persistence and Morse theory for discrete geometric structures
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2024'
...
---
OA_place: publisher
OA_type: hybrid
_id: '15247'
abstract:
- lang: eng
text: Extending the notion of sunflowers, we call a family of at least two sets
an odd-sunflower if every element of the underlying set is contained in an odd
number of sets or in none of them. It follows from the Erdős–Szemerédi conjecture,
recently proved by Naslund and Sawin, that there is a constant <2 such that every
family of subsets of an n-element set that contains no odd-sunflower consists
of at most n sets. We construct such families of size at least 1.5021n. We also
characterize minimal odd-sunflowers of triples.
acknowledgement: We are grateful to Balázs Keszegh, and to the members of the Miklós
Schweitzer Competition committee of 2022 for valuable discussions, and Shira Zerbib
for pointing out several important mathematical typos.
article_number: '105889'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Peter
full_name: Frankl, Peter
last_name: Frankl
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Dömötör
full_name: Pálvölgyi, Dömötör
last_name: Pálvölgyi
citation:
ama: Frankl P, Pach J, Pálvölgyi D. Odd-sunflowers. Journal of Combinatorial
Theory, Series A. 2024;206(8). doi:10.1016/j.jcta.2024.105889
apa: Frankl, P., Pach, J., & Pálvölgyi, D. (2024). Odd-sunflowers. Journal
of Combinatorial Theory, Series A. Elsevier. https://doi.org/10.1016/j.jcta.2024.105889
chicago: Frankl, Peter, János Pach, and Dömötör Pálvölgyi. “Odd-Sunflowers.” Journal
of Combinatorial Theory, Series A. Elsevier, 2024. https://doi.org/10.1016/j.jcta.2024.105889.
ieee: P. Frankl, J. Pach, and D. Pálvölgyi, “Odd-sunflowers,” Journal of Combinatorial
Theory, Series A, vol. 206, no. 8. Elsevier, 2024.
ista: Frankl P, Pach J, Pálvölgyi D. 2024. Odd-sunflowers. Journal of Combinatorial
Theory, Series A. 206(8), 105889.
mla: Frankl, Peter, et al. “Odd-Sunflowers.” Journal of Combinatorial Theory,
Series A, vol. 206, no. 8, 105889, Elsevier, 2024, doi:10.1016/j.jcta.2024.105889.
short: P. Frankl, J. Pach, D. Pálvölgyi, Journal of Combinatorial Theory, Series
A 206 (2024).
corr_author: '1'
date_created: 2024-03-31T22:01:11Z
date_published: 2024-08-01T00:00:00Z
date_updated: 2025-09-04T13:20:39Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jcta.2024.105889
external_id:
arxiv:
- '2310.16701'
isi:
- '001217739200001'
file:
- access_level: open_access
checksum: ffc29d65e712849f0d31009271e06a63
content_type: application/pdf
creator: dernst
date_created: 2025-01-09T08:37:20Z
date_updated: 2025-01-09T08:37:20Z
file_id: '18791'
file_name: 2024_JourCombiTheoryA_Frankl.pdf
file_size: 366029
relation: main_file
success: 1
file_date_updated: 2025-01-09T08:37:20Z
has_accepted_license: '1'
intvolume: ' 206'
isi: 1
issue: '8'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: Journal of Combinatorial Theory, Series A
publication_identifier:
eissn:
- 1096-0899
issn:
- 0097-3165
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Odd-sunflowers
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 206
year: '2024'
...
---
OA_place: publisher
OA_type: hybrid
_id: '15380'
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: "The authors thank Uli Wagner and Emo Welzl for comments on an earlier
version of this paper, and for pointing out related work in the prior literature.\r\nOpen
access funding provided by Institute of Science and Technology (IST Austria). 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: 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. Journal of Applied and
Computational Topology. 2024;8:557-578. doi:10.1007/s41468-024-00173-w'
apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian,
M. (2024). Depth in arrangements: Dehn–Sommerville–Euler relations with applications.
Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-024-00173-w'
chicago: 'Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
and Morteza Saghafian. “Depth in Arrangements: Dehn–Sommerville–Euler Relations
with Applications.” Journal of Applied and Computational Topology. Springer
Nature, 2024. https://doi.org/10.1007/s41468-024-00173-w.'
ieee: 'R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Depth
in arrangements: Dehn–Sommerville–Euler relations with applications,” Journal
of Applied and Computational Topology, vol. 8. Springer Nature, pp. 557–578,
2024.'
ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2024. Depth
in arrangements: Dehn–Sommerville–Euler relations with applications. Journal of
Applied and Computational Topology. 8, 557–578.'
mla: 'Biswas, Ranita, et al. “Depth in Arrangements: Dehn–Sommerville–Euler Relations
with Applications.” Journal of Applied and Computational Topology, vol.
8, Springer Nature, 2024, pp. 557–78, doi:10.1007/s41468-024-00173-w.'
short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal
of Applied and Computational Topology 8 (2024) 557–578.
corr_author: '1'
date_created: 2024-05-12T22:01:03Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-05-14T09:27:57Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s41468-024-00173-w
ec_funded: 1
external_id:
pmid:
- '39308789'
file:
- access_level: open_access
checksum: 0ee15c1493a6413cf356ab2f32c81a9e
content_type: application/pdf
creator: dernst
date_created: 2025-04-23T08:01:36Z
date_updated: 2025-04-23T08:01:36Z
file_id: '19612'
file_name: 2024_JourApplCompTopo_BiswasRa.pdf
file_size: 522831
relation: main_file
success: 1
file_date_updated: 2025-04-23T08:01:36Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 557-578
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: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11658'
relation: earlier_version
status: public
scopus_import: '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
volume: 8
year: '2024'
...
---
_id: '17144'
abstract:
- lang: eng
text: "We prove that the medial axis of closed sets is Hausdorff stable in the following
sense: Let \U0001D4AE ⊆ ℝ^d be a fixed closed set that contains a bounding sphere.
That is, the bounding sphere is part of the set \U0001D4AE. Consider the space
of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant.
The map from this space of diffeomorphisms (endowed with a Banach norm) to the
space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping
a diffeomorphism F to the closure of the medial axis of F(\U0001D4AE), is Lipschitz.
This extends a previous stability result of Chazal and Soufflet on the stability
of the medial axis of C² manifolds under C² ambient diffeomorphisms."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I 02979-N35.\r\nSupported by the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and
the welcome package from IDEX of the Université Cô d'Azur.\r\nWe are greatly indebted
to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher
Fillmore, and Elizabeth Stephenson for early discussions and all members of the
Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape
team (Inria) for the atmosphere in which this research was conducted."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: No
arxiv: 1
author:
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Kourimska H, Lieutier A, Wintraecken M. The medial axis of any closed bounded
set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms.
In: 40th International Symposium on Computational Geometry. Vol 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.69'
apa: 'Kourimska, H., Lieutier, A., & Wintraecken, M. (2024). The medial axis
of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance
Under ambient diffeomorphisms. In 40th International Symposium on Computational
Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.69'
chicago: Kourimska, Hana, André Lieutier, and Mathijs Wintraecken. “The Medial Axis
of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance
Under Ambient Diffeomorphisms.” In 40th International Symposium on Computational
Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.SoCG.2024.69.
ieee: H. Kourimska, A. Lieutier, and M. Wintraecken, “The medial axis of any closed
bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient
diffeomorphisms,” in 40th International Symposium on Computational Geometry,
Athens, Greece, 2024, vol. 293.
ista: 'Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed
bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient
diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 293, 69.'
mla: Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz
Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.”
40th International Symposium on Computational Geometry, vol. 293, 69, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.69.
short: H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium
on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-04-15T07:16:58Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.69
ec_funded: 1
external_id:
arxiv:
- '2212.01118'
file:
- access_level: open_access
checksum: b40ff456c19294adb5d9613fcfd751c6
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:33:40Z
date_updated: 2024-06-17T08:33:40Z
file_id: '17150'
file_name: 2024_LIPICS_Kourimska.pdf
file_size: 1612558
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:33:40Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The medial axis of any closed bounded set Is Lipschitz stable with respect
to the Hausdorff distance Under ambient diffeomorphisms
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17145'
abstract:
- lang: eng
text: Grid peeling is the process of repeatedly removing the convex hull vertices
of the grid points that lie inside a given convex curve. It has been conjectured
that, for a more and more refined grid, grid peeling converges to a continuous
process, the affine curve-shortening flow, which deforms the curve based on the
curvature. We prove this conjecture for one class of curves, parabolas with a
vertical axis, and we determine the value of the constant factor in the formula
that relates the two processes.
acknowledgement: Part of this work was done while G.R. enjoyed the hospitality of
the Institute of Science and Technology Austria (ISTA) as a visiting professor during
his sabbatical in the winter semester 2022/23.
alternative_title:
- LIPIcs
article_number: '76'
article_processing_charge: No
arxiv: 1
author:
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
- first_name: Moritz
full_name: Rüber, Moritz
last_name: Rüber
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: 'Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: 40th International
Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.76'
apa: 'Rote, G., Rüber, M., & Saghafian, M. (2024). Grid peeling of parabolas.
In 40th International Symposium on Computational Geometry (Vol. 293). Athens,
Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.76'
chicago: Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.”
In 40th International Symposium on Computational Geometry, Vol. 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.76.
ieee: G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in 40th
International Symposium on Computational Geometry, Athens, Greece, 2024, vol.
293.
ista: 'Rote G, Rüber M, Saghafian M. 2024. Grid peeling of parabolas. 40th International
Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 293, 76.'
mla: Rote, Günter, et al. “Grid Peeling of Parabolas.” 40th International Symposium
on Computational Geometry, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.76.
short: G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2024-06-17T08:41:56Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.76
external_id:
arxiv:
- '2402.15787'
file:
- access_level: open_access
checksum: fbad1de06383a6b7e8a1cb3e8c7205ce
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:40:04Z
date_updated: 2024-06-17T08:40:04Z
file_id: '17151'
file_name: 2024_LIPICS_Rote.pdf
file_size: 1430896
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:40:04Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Grid peeling of parabolas
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17170'
abstract:
- lang: eng
text: "In this article we extend and strengthen the seminal work by Niyogi, Smale,
and Weinberger on the learning of the homotopy type from a sample of an underlying
space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds
with positive reach embedded in ℝ^d. We extend their results in the following
ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with
lower bounded sectional curvature. - In both types of ambient spaces, we study
sets of positive reach - a significantly more general setting than C² manifolds
- as well as general manifolds of positive reach. - The sample P of a set (or
a manifold) \U0001D4AE of positive reach may be noisy. We work with two one-sided
Hausdorff distances - ε and δ - between P and \U0001D4AE. We provide tight bounds
in terms of ε and δ, that guarantee that there exists a parameter r such that
the union of balls of radius r centred at the sample P deformation-retracts to
\U0001D4AE. We exhibit their tightness by an explicit construction. We carefully
distinguish the roles of δ and ε. This is not only essential to achieve tight
bounds, but also sensible in practical situations, since it allows one to adapt
the bound according to sample density and the amount of noise present in the sample
separately."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I 02979-N35.\r\nWintraecken, Mathijs: Supported by
the European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant
No. M-3073, and the welcome package from IDEX of the Université Côte d'Azur."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Dominique
full_name: Attali, Dominique
last_name: Attali
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Ishika
full_name: Ghosh, Ishika
id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff
last_name: Ghosh
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Attali D, Kourimska H, Fillmore CD, et al. Tight bounds for the learning of
homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and
of Riemannian manifolds. In: 40th International Symposium on Computational
Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19.
doi:10.4230/LIPIcs.SoCG.2024.11'
apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson,
E. R., & Wintraecken, M. (2024). Tight bounds for the learning of homotopy
à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian
manifolds. In 40th International Symposium on Computational Geometry (Vol.
293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2024.11'
chicago: Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh,
André Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “Tight Bounds
for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of
Euclidean Spaces and of Riemannian Manifolds.” In 40th International Symposium
on Computational Geometry, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.11.
ieee: D. Attali et al., “Tight bounds for the learning of homotopy à la Niyogi,
Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,”
in 40th International Symposium on Computational Geometry, Athens, Greece,
2024, vol. 293, p. 11:1-11:19.
ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken
M. 2024. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
for subsets of euclidean spaces and of Riemannian manifolds. 40th International
Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 293, 11:1-11:19.'
mla: Attali, Dominique, et al. “Tight Bounds for the Learning of Homotopy à La Niyogi,
Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.”
40th International Symposium on Computational Geometry, vol. 293, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:10.4230/LIPIcs.SoCG.2024.11.
short: D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson,
M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
date_created: 2024-06-25T11:45:58Z
date_published: 2024-06-06T00:00:00Z
date_updated: 2025-04-15T07:16:57Z
day: '06'
ddc:
- '516'
department:
- _id: GradSch
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.11
ec_funded: 1
external_id:
arxiv:
- '2206.10485'
file:
- access_level: open_access
checksum: 6a2ddc8b51aa58f197a8b294750f1f8d
content_type: application/pdf
creator: cfillmor
date_created: 2024-06-25T11:47:26Z
date_updated: 2024-06-25T11:47:26Z
file_id: '17171'
file_name: LIPIcs.SoCG.2024.11.pdf
file_size: 20886142
relation: main_file
success: 1
file_date_updated: 2024-06-25T11:47:26Z
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 11:1-11:19
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959773164'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
for subsets of euclidean spaces and of Riemannian manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '17190'
abstract:
- lang: eng
text: "For a locally finite set, \U0001D434⊆ℝ\U0001D451\r\n, the \U0001D458\r\nth
Brillouin zone of \U0001D44E∈\U0001D434\r\n is the region of points \U0001D465∈ℝ\U0001D451\r\n
for which ‖\U0001D465−\U0001D44E‖\r\n is the \U0001D458\r\nth smallest among the
Euclidean distances between \U0001D465\r\n and the points in \U0001D434\r\n. If
\U0001D434\r\n is a lattice, the \U0001D458\r\nth Brillouin zones of the points
in \U0001D434\r\n are translates of each other, and together they tile space.
Depending on the value of \U0001D458\r\n, they express medium- or long-range order
in the set. We study fundamental geometric and combinatorial properties of Brillouin
zones, focusing on the integer lattice and its perturbations. Our results include
the stability of a Brillouin zone under perturbations, a linear upper bound on
the number of chambers in a zone for lattices in ℝ2\r\n, and the convergence of
the maximum volume of a chamber to zero for the integer lattice."
acknowledgement: The second author is partially supported by the Alexander von Humboldt
Foundation. The sixth author is supported by the European Union's Horizon 2020 research
and innovation programme under Marie Sklodowska-Curie grant agreement 754411, and
by Austrian Science Fund(FWF) grant M-3073. All other authors are supported by European
Research Council (ERC) grant 788183, by the Wittgenstein Prize, by Austrian Science
Fund (FWF) grant Z 342-N31, and by the DFG Collaborative Research Center TRR 109,
Austrian Science Fund (FWF) grant I 02979-N35.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Alexey
full_name: Garber, Alexey
last_name: Garber
- first_name: Mohadese
full_name: Ghafaris, Mohadese
last_name: Ghafaris
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Morteza
full_name: Saghafiant, Morteza
last_name: Saghafiant
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M.
Brillouin zones of integer lattices and their perturbations. SIAM Journal on
Discrete Mathematics. 2024;38(2):1784-1807. doi:10.1137/22M1489071
apa: Edelsbrunner, H., Garber, A., Ghafaris, M., Heiss, T., Saghafiant, M., &
Wintraecken, M. (2024). Brillouin zones of integer lattices and their perturbations.
SIAM Journal on Discrete Mathematics. Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/22M1489071
chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafaris, Teresa Heiss,
Morteza Saghafiant, and Mathijs Wintraecken. “Brillouin Zones of Integer Lattices
and Their Perturbations.” SIAM Journal on Discrete Mathematics. Society
for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/22M1489071.
ieee: H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, and M. Wintraecken,
“Brillouin zones of integer lattices and their perturbations,” SIAM Journal
on Discrete Mathematics, vol. 38, no. 2. Society for Industrial and Applied
Mathematics, pp. 1784–1807, 2024.
ista: Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M.
2024. Brillouin zones of integer lattices and their perturbations. SIAM Journal
on Discrete Mathematics. 38(2), 1784–1807.
mla: Edelsbrunner, Herbert, et al. “Brillouin Zones of Integer Lattices and Their
Perturbations.” SIAM Journal on Discrete Mathematics, vol. 38, no. 2, Society
for Industrial and Applied Mathematics, 2024, pp. 1784–807, doi:10.1137/22M1489071.
short: H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, M. Wintraecken,
SIAM Journal on Discrete Mathematics 38 (2024) 1784–1807.
corr_author: '1'
date_created: 2024-06-30T22:01:05Z
date_published: 2024-06-07T00:00:00Z
date_updated: 2025-09-08T08:06:04Z
day: '07'
department:
- _id: HeEd
doi: 10.1137/22M1489071
ec_funded: 1
external_id:
arxiv:
- '2204.01077'
isi:
- '001292728600001'
intvolume: ' 38'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2204.01077
month: '06'
oa: 1
oa_version: Preprint
page: 1784-1807
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
issn:
- 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Brillouin zones of integer lattices and their perturbations
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 38
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18556'
abstract:
- lang: eng
text: Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined
length of the minimum spanning trees of B and A⧵B divided by the length of the
minimum spanning tree of A. The question of the supremum, over all sets A, of
the maximum, over all subsets B, is related to the Steiner ratio, and we prove
this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional
lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin
the most difficult of these results is the upper bound for the inf-max, which
we prove by showing that the hexagonal lattice cannot have MST-ratio larger than
1.25.
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_number: '3'
article_processing_charge: Yes
arxiv: 1
author:
- 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: Ondrej
full_name: Draganov, Ondrej
id: 2B23F01E-F248-11E8-B48F-1D18A9856A87
last_name: Draganov
orcid: 0000-0003-0464-3823
- 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: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean
MST-ratio for bi-colored lattices. In: 32nd International Symposium on Graph
Drawing and Network Visualization. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.GD.2024.3'
apa: 'Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian,
M. (2024). The Euclidean MST-ratio for bi-colored lattices. In 32nd International
Symposium on Graph Drawing and Network Visualization (Vol. 320). Vienna, Austria:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.3'
chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner,
and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In 32nd
International Symposium on Graph Drawing and Network Visualization, Vol. 320.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.GD.2024.3.
ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian,
“The Euclidean MST-ratio for bi-colored lattices,” in 32nd International Symposium
on Graph Drawing and Network Visualization, Vienna, Austria, 2024, vol. 320.
ista: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The
Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph
Drawing and Network Visualization. GD: Graph Drawing and Network Visualization,
LIPIcs, vol. 320, 3.'
mla: Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored
Lattices.” 32nd International Symposium on Graph Drawing and Network Visualization,
vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.GD.2024.3.
short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:,
32nd International Symposium on Graph Drawing and Network Visualization, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-20
location: Vienna, Austria
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2024-09-18
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-28T00:00:00Z
date_updated: 2025-12-02T13:50:50Z
day: '28'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.GD.2024.3
ec_funded: 1
external_id:
arxiv:
- '2403.10204'
isi:
- '001540278400001'
file:
- access_level: open_access
checksum: 5f9b35e115c3d375e99be78da9054cb4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T07:49:25Z
date_updated: 2024-11-18T07:49:25Z
file_id: '18560'
file_name: 2024_LIPIcs_CultreradiMontesano.pdf
file_size: 908541
relation: main_file
success: 1
file_date_updated: 2024-11-18T07:49:25Z
has_accepted_license: '1'
intvolume: ' 320'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: 32nd International Symposium on Graph Drawing and Network Visualization
publication_identifier:
isbn:
- '9783959773430'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Euclidean MST-ratio for bi-colored lattices
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: 320
year: '2024'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '18604'
abstract:
- lang: eng
text: 'A face in a curve arrangement is called popular if it is bounded by the same
curve multiple times. Motivated by the automatic generation of curved nonogram
puzzles, we investigate possibilities to eliminate the popular faces in an arrangement
by inserting a single additional curve. This turns out to be NP-hard; however,
it becomes tractable when the number of popular faces is small: We present a randomized
FPT-time algorithm where the parameter is the number of popular faces.'
acknowledgement: "This work was initiated at the 16th European Research Week on Geometric
Graphs in Strobl in 2019. A.W. has been supported by the Austrian Science Fund (FWF):
W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]
and by the NWO Gravitation project NETWORKS under grant no. 024.002.003. Part of
the work was done while A.W. was emplyed at Graz University of Technology. Preliminary
versions of this work have been presented at the 38th European Workshop on Computational
Geometry (EuroCG\r\n2022) in Perugia [10] and at the 31st International Symposium
on Graph Drawing and Network Visualization (GD 2023) in Isola delle Femmine [11]."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Phoebe
full_name: De Nooijer, Phoebe
last_name: De Nooijer
- first_name: Soeren
full_name: Terziadis, Soeren
last_name: Terziadis
- first_name: Alexandra
full_name: Weinberger, Alexandra
last_name: Weinberger
- 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: Tamara
full_name: Mchedlidze, Tamara
last_name: Mchedlidze
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
citation:
ama: De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve
arrangements. Journal of Graph Algorithms and Applications. 2024;28(2):47-82.
doi:10.7155/jgaa.v28i2.2988
apa: De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T.,
Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements.
Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.v28i2.2988
chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová,
Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in
Curve Arrangements.” Journal of Graph Algorithms and Applications. Brown
University, 2024. https://doi.org/10.7155/jgaa.v28i2.2988.
ieee: P. De Nooijer et al., “Removing popular faces in curve arrangements,”
Journal of Graph Algorithms and Applications, vol. 28, no. 2. Brown University,
pp. 47–82, 2024.
ista: De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler
M, Rote G. 2024. Removing popular faces in curve arrangements. Journal of Graph
Algorithms and Applications. 28(2), 47–82.
mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.”
Journal of Graph Algorithms and Applications, vol. 28, no. 2, Brown University,
2024, pp. 47–82, doi:10.7155/jgaa.v28i2.2988.
short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M.
Löffler, G. Rote, Journal of Graph Algorithms and Applications 28 (2024) 47–82.
corr_author: '1'
date_created: 2024-12-01T23:01:54Z
date_published: 2024-11-03T00:00:00Z
date_updated: 2024-12-03T09:49:18Z
day: '03'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.7155/jgaa.v28i2.2988
external_id:
arxiv:
- '2202.12175'
file:
- access_level: open_access
checksum: be611da6f9d790dc980d6fb7283fe889
content_type: application/pdf
creator: dernst
date_created: 2024-12-03T09:45:00Z
date_updated: 2024-12-03T09:45:00Z
file_id: '18609'
file_name: 2024_JourGraphAlgorithms_deNooijer.pdf
file_size: 1582493
relation: main_file
success: 1
file_date_updated: 2024-12-03T09:45:00Z
has_accepted_license: '1'
intvolume: ' 28'
issue: '2'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 47-82
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
scopus_import: '1'
status: public
title: Removing popular faces in curve arrangements
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: 28
year: '2024'
...