Computing the Betti Numbers of Arrangements in Practice

摘要

We describe an algorithm for computing the zero-th and the first Betti numbers of the union of n simply connected compact semi-algebraic sets in R~k, where each such set is defined by a constant number of polynomials of constant degrees. The complexity of the algorithm is O(n~3). We also describe an implementation of this algorithm in the particular case of arrangements of ellipsoids in R~3 and describe some of our results.