# Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

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.

-
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