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](https://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope) " Algorithm for finding the volume of a convex polytope",


[paper by J. Lawrence 1991](http://fma2.math.uni-magdeburg.de/~henk/lectures/konvexgeometrie%2520analytische%2520aspekte/seminar/lawrence&polytope%2520volume%2520computation.pdf) "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.



Complexity of convex polytope volume calculation  ? (Volume of Voronoi cell) (Error probability)
See [this very nice paper of Bringmann and Fried.](http://www.mpi-inf.mpg.de/~tfried/paper/CGTA1.pdf)


