Maximum Betti Numbers of Čech Complexes

Edelsbrunner, H. and Pach, János (2024) Maximum Betti Numbers of Čech Complexes. In: 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics, LIPIcs (293). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Wadern, p. 53. ISBN 9783959773164

Preview

Text 2310.14801v1.pdf Download (799kB) | Preview

Abstract

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 Rd and any radius satisfies βp = O(Nm), 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 R3 and two radii such that the first Betti number of the Čech complex at one radius is (n + 1)2 − 1, and the second Betti number of the Čech complex at the other radius is n2. In particular, there is an arrangement of n contruent balls in R3 that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry. © Herbert Edelsbrunner and János Pach.

Actions (login required)

Edit Item