Numerical computation of the homology of basic semialgebraic sets

Semialgebraic sets (that is subsets of Euclidean spaces defined by polynomial equations and inequalities) come in a wide variety of shapes. This raises the problem of describing a given specimen, from basic features like the number of connected components, to finer ones, like homology.

Following a well-known approach, we compute the homology using approximations by point cloud. We show how to ensure correctness and give complexity bounds in terms of the conditioning of the input equations. A probabilistic analysis shows that outside of a vanishingly small subset of the input space, the complexity is single exponential with respect to the number of variables. This improves upon the previously-known double exponential complexity bounds.