most recent 30 from http://mathoverflow.net 2013-06-19T15:32:37Z http://mathoverflow.net/feeds/question/101240 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101240/complexity-of-convex-polytope-volume-calculation-volume-of-voronoi-cell-err Alexander Chervov 2012-07-03T16:25:42Z 2012-07-03T17:43:34Z

<p>Assume I have polytope in R^k given by N (k&lt;&lt; N) linear inequalities (A_i x &lt; b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity known ? ) </p> <p>Example: k =120, N=2^24, so probably the only method for practical calculation is Monte-Carlo, am I right ?</p> <p>Actually my polytope is Voronoi cell for some set of N points, but probably this will not help me, am I right ?</p> <hr> <p>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: <a href="http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope" rel="nofollow">MO question</a> " Algorithm for finding the volume of a convex polytope",</p> <p><a href="http://fma2.math.uni-magdeburg.de/~henk/lectures/konvexgeometrie%2520analytische%2520aspekte/seminar/lawrence&amp;polytope%2520volume%2520computation.pdf" rel="nofollow">paper by J. Lawrence 1991 </a>"POLYTOPE VOLUME COMPUTATION", see theorem page 260 bottom.</p> <hr> <p>Motivation.</p> <p>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.</p> <p>Typical algorithm would be just such a sent signal "s" to which Voronoi cell point "r" belongs to.</p> <p>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.</p> <p>PS</p> <p>Well actually noise is usually Gaussian, but for simplicity I may take uniform.</p>

http://mathoverflow.net/questions/101240/complexity-of-convex-polytope-volume-calculation-volume-of-voronoi-cell-err/101245#101245 Igor Rivin 2012-07-03T17:43:34Z 2012-07-03T17:43:34Z

<p>See <a href="http://www.mpi-inf.mpg.de/~tfried/paper/CGTA1.pdf" rel="nofollow">this very nice paper of Bringmann and Fried.</a></p>