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.
