Estimating the volume of a semialgebraic set from above

Question

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

Answer 1

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...

UPDATE As the OP points out in the comment, the method as described only works for compact semi-algebraic sets (at least in so far as requiring upper bounds). There is a better (as in, theoretically faster) method that also works for compact sets only, due to Henrion/Lasserre/Savognan.