4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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"! :-) $\endgroup$ – Joseph O'Rourke Jul 3 '12 at 19:07
3
$\begingroup$

See this very nice paper of Bringmann and Fried.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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