# Estimating the volume of a semialgebraic set from above

Suppose $S$ is a subset of $\mathbb{R}^n$ of finite volume defined by a system of finitely many polynomial inequalities with integer coefficients. Can anyone describe an algorithm that, given such a system of inequalities, generates a sequence of rational numbers that converges to the volume of $S$ from above?

This question expands a comment of Andrej Bauer to a related question.

This question was posted on math stackexchange here. There were no responses.

The case that baffles me is when $S$ is unbounded. The obvious approach would be to find some general way to enlarge $S$ by "a little bit" to a set whose volume is easy to compute. But I don't see how to do this.

Actually, I cannot even describe an algorithm to determine whether or not $S$ has finite volume, and such an algorithm might give a good start to solving the original problem

-

Here is an algorithm: partition $\mathbb{R}^n$ into cubes of side $1/k.$ For each cube $C_i$, use your favorite quantifier elimination algorithm to check whether the set $S$ intersects it. Then, your bound is the number of cubes $S$ intersects divided by $k^n,$ which is obviously rational, and just as obviously converges to the volume of $S$ from above. You may argue that your set $S$ is not known to be bounded, so on $k$-th step make your cubes fill a cube of side $k.$ Granted, the algorithm will be rather slow, but given that even computing the volume of a polytope (that is, a semi-algebraic set where the inequalities are linear) is known to be hard, no really quick algorithm is likely...
@Igor: In the case that $S$ is unbounded, why does your method give estimates that are larger than the volume of $S$? – SJR Sep 11 '12 at 1:16