---
_id: '17146'
abstract:
- lang: eng
  text: The Upper Bound Theorem for convex polytopes implies that the p-th Betti number
    of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p
    = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions,
    which prove that this upper bound is asymptotically tight. For example, we describe
    a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number
    of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of
    the Čech complex at the other radius is n². In particular, there is an arrangement
    of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers
    a long-standing open question in computational geometry.
acknowledgement: "The first author is supported by the European Research Council (ERC),
  grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian
  Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the
  European Research Council (ERC), grant \"GeoScape\" and by the Hungarian Science
  Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein
  Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.\r\nThe authors thank Matt
  Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart
  for early discussions on the linked circles construction in three dimensions, and
  Gábor Tardos for helpful remarks and suggestions."
alternative_title:
- LIPIcs
article_number: '53'
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: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
citation:
  ama: 'Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: <i>40th
    International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.53">10.4230/LIPIcs.SoCG.2024.53</a>'
  apa: 'Edelsbrunner, H., &#38; Pach, J. (2024). Maximum Betti numbers of Čech complexes.
    In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens,
    Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.53">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>'
  chicago: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.”
    In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.53">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>.
  ieee: H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in
    <i>40th International Symposium on Computational Geometry</i>, Athens, Greece,
    2024, vol. 293.
  ista: 'Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th
    International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 293, 53.'
  mla: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.”
    <i>40th International Symposium on Computational Geometry</i>, vol. 293, 53, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.53">10.4230/LIPIcs.SoCG.2024.53</a>.
  short: H. Edelsbrunner, J. Pach, 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: 2025-12-01T15:19:20Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.53
ec_funded: 1
external_id:
  arxiv:
  - '2310.14801'
file:
- access_level: open_access
  checksum: 5442d44fb89d77477a87668d6e61aac9
  content_type: application/pdf
  creator: dernst
  date_created: 2024-06-17T08:46:33Z
  date_updated: 2024-06-17T08:46:33Z
  file_id: '17152'
  file_name: 2024_LIPICS_Edelsbrunner.pdf
  file_size: 766562
  relation: main_file
  success: 1
file_date_updated: 2024-06-17T08:46:33Z
has_accepted_license: '1'
intvolume: '       293'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
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: 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: 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'
related_material:
  record:
  - id: '20657'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Maximum Betti numbers of Čech complexes
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'
...