Computing the Betti numbers of arrangements via spectral sequences

摘要

In this paper, we consider the problem of computing the Betti numbers of an arrangement of n compact semi-algebraic sets, S1,…,Sn⊂Rk, where each Si is described using a constant number of polynomials with degrees bounded by a constant. Such arrangements are ubiquitous in computational geometry. We give an algorithm for computing ℓth Betti number, βℓ(⋃i=1nSi), 0⩽ℓ⩽k−1, using O(nℓ+2) algebraic operations. Additionally, one has to perform linear algebra on integer matrices of size bounded by O(nℓ+2). All previous algorithms for computing the Betti numbers of arrangements, triangulated the whole arrangement giving rise to a complex of size O(n2k) in the worst case. Thus, the complexity of computing the Betti numbers (other than the zeroth one) for these algorithms was O(n2k). To our knowledge this is the first algorithm for computing βℓ(⋃i=1nSi) that does not rely on such a global triangulation, and has a graded complexity which depends on ℓ.