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, S 1 ; : : : ; S n R , where each S i 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=1 S i ); 0 ` k 1, using ) algebraic operations. Additionally, one has to perform linear algebra on integer matrices of size bounded by O(n ). All previous algorithms for computing the Betti numbers of arrangements, triangulated the whole arrangement giving rise to a complex of size O(n ) in the worst case. Thus, the complexity of computing the Betti numbers (other than the zero-th one) for these algorithms was O(n ). To our knowledge this is the rst algorithm for computing ` ([ i=1 S i ) that does not rely on such a global triangulation, and has a graded complexity which depends on `. Key words: Semi-algebraic Sets, Betti Numbers, Spectral Sequence