Computing the Betti numbers of arrangements via spectral sequences

✍ Scribed by Saugata Basu

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 274 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00009-6

✦ Synopsis

In this paper, we consider the problem of computing the Betti numbers of an arrangement of n compact semi-algebraic sets, S 1 ; y; S n CR k ; 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 cth Betti number, b c ð S n i¼1 S i Þ; 0pcpk À 1; using Oðn cþ2 Þ algebraic operations. Additionally, one has to perform linear algebra on integer matrices of size bounded by Oðn cþ2 Þ: All previous algorithms for computing the Betti numbers of arrangements, triangulated the whole arrangement giving rise to a complex of size Oðn 2 k Þ in the worst case. Thus, the complexity of computing the Betti numbers (other than the zeroth one) for these algorithms was Oðn 2 k Þ: To our knowledge this is the first algorithm for computing b c ð S n i¼1 S i Þ that does not rely on such a global triangulation, and has a graded complexity which depends on c: