Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

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

share|improve this answer
    
@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
    
@SJR: Ah, good point. –  Igor Rivin Sep 11 '12 at 1:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.