---
OA_place: publisher
OA_type: gold
_id: '20004'
abstract:
- lang: eng
  text: "A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize
    McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due
    to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level
    in a simple arrangement of n hemispheres in S^d is maximized for arrangements
    that are polar duals of neighborly d-polytopes. We prove this conjecture in the
    case n = d+4. By Gale duality, this implies the following result about crossing
    numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of
    n unit vectors connected by spherical arcs), the number of crossings is at least
    1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every
    open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.\r\nMoreover,
    we determine the space of all linear and affine relations that hold between the
    face numbers of levels in simple arrangements of n hemispheres in S^d. This completes
    a long line of research on such relations, answers a question posed by Andrzejak
    and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville
    relations generate all linear relations between the face numbers of simple polytopes
    (which correspond to the 0-level).\r\nTo prove these results, we introduce the
    notion of the g-matrix, which encodes the face numbers of levels in an arrangement
    and generalizes the classical g-vector of a polytope."
alternative_title:
- LIPIcs
article_number: '75'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Elizaveta
  full_name: Streltsova, Elizaveta
  id: 57a170da-dc96-11ea-b7c8-ab3565071bf7
  last_name: Streltsova
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix,
    and applications to crossing numbers. In: <i> 41st International Symposium on
    Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2025. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.75">10.4230/LIPIcs.SoCG.2025.75</a>'
  apa: 'Streltsova, E., &#38; Wagner, U. (2025). Levels in arrangements: Linear relations,
    the g-matrix, and applications to crossing numbers. In <i> 41st International
    Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.75">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>'
  chicago: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear
    Relations, the g-Matrix, and Applications to Crossing Numbers.” In <i> 41st International
    Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.75">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>.'
  ieee: 'E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the
    g-matrix, and applications to crossing numbers,” in <i> 41st International Symposium
    on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.'
  ista: 'Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the
    g-matrix, and applications to crossing numbers.  41st International Symposium
    on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs,
    vol. 332, 75.'
  mla: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations,
    the g-Matrix, and Applications to Crossing Numbers.” <i> 41st International Symposium
    on Computational Geometry</i>, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2025, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.75">10.4230/LIPIcs.SoCG.2025.75</a>.'
  short: E. Streltsova, U. Wagner, in:,  41st International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
  end_date: 2025-06-27
  location: Kanazawa, Japan
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:22Z
date_published: 2025-06-20T00:00:00Z
date_updated: 2025-07-14T07:19:19Z
day: '20'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2025.75
external_id:
  arxiv:
  - '2504.07752'
  - '2504.07770'
file:
- access_level: open_access
  checksum: a8f7feb1aa3b896e31195841a989d622
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T07:11:04Z
  date_updated: 2025-07-14T07:11:04Z
  file_id: '20015'
  file_name: 2025_LIPIcs.SoCG_Streltsova.pdf
  file_size: 952807
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T07:11:04Z
has_accepted_license: '1'
intvolume: '       332'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
publication: ' 41st International Symposium on Computational Geometry'
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773706'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Levels in arrangements: Linear relations, the g-matrix, and applications to
  crossing numbers'
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: 332
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20005'
abstract:
- lang: eng
  text: "We generalize a classical result by Boris Delaunay that introduced Delaunay
    triangulations. In particular, we prove that for a locally finite and coarsely
    dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly
    binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose
    exactly k points of A. We extend this result to the cases in which the points
    are weighted, and when A contains only finitely many points in ℝ^d or in \U0001D54A^d.
    Furthermore, we use the result to give a new geometric proof for the fact that
    volumes of hypersimplices are Eulerian numbers."
acknowledgement: "Herbert Edelsbrunner: partially supported by the Wittgenstein Prize,
  Austrian Science\r\nFund (FWF), grant no. Z 342-N31, and by the DFG Collaborative
  Research Center TRR 109,\r\nAustrian Science Fund (FWF), grant no. I 02979-N35.\r\nAlexey
  Garber: partially supported by the Simons Foundation.\r\nMorteza Saghafian: partially
  supported by the Wittgenstein Prize, Austrian Science Fund (FWF),\r\ngrant no. Z
  342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund
  (FWF), grant no. I 02979-N35"
alternative_title:
- LIPIcs
article_number: '43'
article_processing_charge: Yes
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: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
citation:
  ama: 'Edelsbrunner H, Garber A, Saghafian M. On spheres with k points inside. In:
    <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.43">10.4230/LIPIcs.SoCG.2025.43</a>'
  apa: 'Edelsbrunner, H., Garber, A., &#38; Saghafian, M. (2025). On spheres with
    k points inside. In <i>41st International Symposium on Computational Geometry</i>
    (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.43">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>'
  chicago: Edelsbrunner, Herbert, Alexey Garber, and Morteza Saghafian. “On Spheres
    with k Points Inside.” In <i>41st International Symposium on Computational Geometry</i>,
    Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.43">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>.
  ieee: H. Edelsbrunner, A. Garber, and M. Saghafian, “On spheres with k points inside,”
    in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan,
    2025, vol. 332.
  ista: 'Edelsbrunner H, Garber A, Saghafian M. 2025. On spheres with k points inside.
    41st International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 332, 43.'
  mla: Edelsbrunner, Herbert, et al. “On Spheres with k Points Inside.” <i>41st International
    Symposium on Computational Geometry</i>, vol. 332, 43, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2025, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.43">10.4230/LIPIcs.SoCG.2025.43</a>.
  short: H. Edelsbrunner, A. Garber, M. Saghafian, in:, 41st International Symposium
    on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2025.
conference:
  end_date: 2025-06-27
  location: Kanazawa, Japan
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:22Z
date_published: 2025-06-20T00:00:00Z
date_updated: 2025-07-14T07:26:14Z
day: '20'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2025.43
external_id:
  arxiv:
  - '2410.21204'
file:
- access_level: open_access
  checksum: b5313ed8575ea87913c71a6e3c7513c8
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T07:24:22Z
  date_updated: 2025-07-14T07:24:22Z
  file_id: '20016'
  file_name: 2025_LIPIcs.SoCG_Edelsbrunner.pdf
  file_size: 661893
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T07:24:22Z
has_accepted_license: '1'
intvolume: '       332'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _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: 41st International Symposium on Computational Geometry
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773706'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: On spheres with k points inside
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: 332
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20006'
abstract:
- lang: eng
  text: In numerous fields, dynamic time series data require continuous updates, necessitating
    efficient data processing techniques for accurate analysis. This paper examines
    the banana tree data structure, specifically designed to efficiently maintain
    the multi-scale topological descriptor commonly known as persistent homology for
    dynamically changing time series data. We implement this data structure and conduct
    an experimental study to assess its properties and runtime for update operations.
    Our findings indicate that banana trees are highly effective with unbiased random
    data, outperforming state-of-the-art static algorithms in these scenarios. Additionally,
    our results show that real-world time series share structural properties with
    unbiased random walks, suggesting potential practical utility for our implementation.
acknowledgement: "Lara Ost: Supported by the Vienna Graduate School on Computational
  Optimization\r\n(VGSCO), FWF project no. W1260-N35.\r\nSebastiano Cultrera di Montesano:
  Supported by the Eric and Wendy Schmidt Center at the Broad Institute of MIT and
  Harvard.\r\nHerbert Edelsbrunner: Partially supported by the Wittgenstein Prize,
  FWF grant no. Z 342-N31,\r\nand by the DFG Collaborative Research Center TRR 109,
  FWF grant no. I 02979-N35."
alternative_title:
- LIPIcs
article_number: '71'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Lara
  full_name: Ost, Lara
  last_name: Ost
- 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
citation:
  ama: 'Ost L, Cultrera di Montesano S, Edelsbrunner H. Banana trees for the persistence
    in time series experimentally. In: <i>41st International Symposium on Computational
    Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.71">10.4230/LIPIcs.SoCG.2025.71</a>'
  apa: 'Ost, L., Cultrera di Montesano, S., &#38; Edelsbrunner, H. (2025). Banana
    trees for the persistence in time series experimentally. In <i>41st International
    Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.71">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>'
  chicago: Ost, Lara, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner.
    “Banana Trees for the Persistence in Time Series Experimentally.” In <i>41st International
    Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.71">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>.
  ieee: L. Ost, S. Cultrera di Montesano, and H. Edelsbrunner, “Banana trees for the
    persistence in time series experimentally,” in <i>41st International Symposium
    on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.
  ista: 'Ost L, Cultrera di Montesano S, Edelsbrunner H. 2025. Banana trees for the
    persistence in time series experimentally. 41st International Symposium on Computational
    Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 71.'
  mla: Ost, Lara, et al. “Banana Trees for the Persistence in Time Series Experimentally.”
    <i>41st International Symposium on Computational Geometry</i>, vol. 332, 71, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2025.71">10.4230/LIPIcs.SoCG.2025.71</a>.
  short: L. Ost, S. Cultrera di Montesano, H. Edelsbrunner, in:, 41st International
    Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2025.
conference:
  end_date: 2025-06-27
  location: Kanazawa, Japan
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:22Z
date_published: 2025-06-20T00:00:00Z
date_updated: 2025-12-30T11:04:33Z
day: '20'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2025.71
external_id:
  arxiv:
  - '2405.17920'
file:
- access_level: open_access
  checksum: 3a4a7a707a56e0cfdf51428782dee55a
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T08:23:38Z
  date_updated: 2025-07-14T08:23:38Z
  file_id: '20017'
  file_name: 2025_LIPIcs.SoCG_Ost.pdf
  file_size: 834623
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T08:23:38Z
has_accepted_license: '1'
intvolume: '       332'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
  grant_number: W1260-N35
  name: Vienna Graduate School on Computational Optimization
- _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: 41st International Symposium on Computational Geometry
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773706'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  link:
  - relation: software
    url: https://github.com/laraost/BananaPersist
scopus_import: '1'
status: public
title: Banana trees for the persistence in time series experimentally
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: 332
year: '2025'
...