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

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity known ? )

Example: k =120, N=2^24, so probably the only method for practical calculation is Monte-Carlo, am I right ?

Actually my polytope is Voronoi cell for some set of N points, but probably this will not help me, am I right ?


I have googled for some time, and it seems to me my guesses are correct, but I would prefer to have a comment from expert to confirm my understandings. Here are some links: MO question " Algorithm for finding the volume of a convex polytope",

paper by J. Lawrence 1991 "POLYTOPE VOLUME COMPUTATION", see theorem page 260 bottom.


Motivation.

This problem can be related to the standard telecommunication problem - calculation of error probability for transmission over noisy channel. Consider space R^k of "all possible signals" choose $N$ points in R^k, these points are "possible sent signals". Assume received signal r = s + noise. The task is to restore sent signal from received signal.

Typical algorithm would be just such a sent signal "s" to which Voronoi cell point "r" belongs to.

Assuming that "noise" is uniformly distributed over some cube $[-\delta, \delta]^k$, the probability of correct detection would be intersection of the Voronoi cell and this cube divided by cube volume.

PS

Well actually noise is usually Gaussian, but for simplicity I may take uniform.

share|improve this question
    
See the earlier MO question, "Algorithm for finding the volume of a convex polytope" mathoverflow.net/questions/979/… One key paper cited there has the title "Computing the volume is difficult"! :-) –  Joseph O'Rourke Jul 3 '12 at 19:07
add comment

1 Answer

up vote 2 down vote accepted

See this very nice paper of Bringmann and Fried.

share|improve this answer
    
@Igor thank you ! –  Alexander Chervov Jul 4 '12 at 5:58
add comment

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.