2026-08-15T12:24:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19998 2024-06-06T06:21:15Z ddc:004 open_access

Maximum Betti Numbers of Čech Complexes Edelsbrunner, Herbert Pach, János Discrete geometry computational topology Čech complexes Delaunay mosaics Alpha complexes Betti numbers extremal questions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Herbert Edelsbrunner and János Pach 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.53 urn:nbn:de:0030-drops-199981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.53 eng https://creativecommons.org/licenses/by/4.0/legalcode