---
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
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'
...