262:
The given convex body can be approximated by a sequence of nested bodies, eventually reaching one of known volume (a hypersphere), with this approach used to estimate the factor by which the volume changes at each step of this sequence. Multiplying these factors gives the approximate volume of the
258:, it is possible to compare the volumes of two convex bodies, one nested within another, when their volumes are within a small factor of each other. The basic idea is to generate random points within the outer of the two bodies, and to count how often those points are also within the inner body.
32:. Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a
278:
Although the time for this algorithm is polynomial, it has a high exponent. Subsequent authors improved the running time of this method by providing more quickly mixing Markov chains for the same problem.
203:(MCMC) method, it is possible to generate points that are nearly uniformly randomly distributed within a given convex body. The basic scheme of the algorithm is a nearly uniform sampling from within
193:
749:
624:
81:
241:
221:
165:
145:
121:
101:
287:
The polynomial-time approximability result has been generalized to more complex structures such as the union and intersection of objects. This relates to
639:
753:
549:
57:
358:
313:
251:, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.
865:
860:
60:
for the problem, providing a sharp contrast between the capabilities of randomized and deterministic algorithms.
510:
506:
40:
can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is
790:
413:
288:
29:
170:
248:
200:
711:
586:
66:
37:
17:
791:"Approximating the volume of unions and intersections of high-dimensional geometric objects"
701:
660:
576:
461:(1991), "A random polynomial-time algorithm for approximating the volume of convex bodies",
776:
688:
647:
486:
434:
391:
336:
824:
664:
580:
8:
836:
802:
555:
490:
463:
353:
255:
226:
206:
150:
130:
106:
86:
532:
Proceedings of the Twenty-Third Annual ACM Symposium on Theory of
Computing (STOC '91)
828:
545:
559:
494:
840:
820:
812:
762:
676:
635:
572:
535:
527:
472:
458:
422:
377:
367:
349:
322:
53:
41:
308:
816:
772:
705:
684:
643:
523:
482:
430:
387:
332:
267:
33:
767:
454:
408:
124:
49:
854:
832:
680:
667:(1993), "Random walks in a convex body and an improved volume algorithm",
540:
477:
450:
404:
311:(1986), "A geometric inequality and the complexity of computing volume",
244:
45:
25:
372:
327:
123:-dimensional Euclidean space by assuming the existence of a membership
640:
10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X
63:
The main result of the paper is a randomized algorithm for finding an
411:(1988), "On the complexity of computing the volume of a polyhedron",
382:
426:
807:
530:(1991), "Sampling and Integration of Near Log-concave Functions",
28:, a problem that can also be used to model many other problems in
21:
571:
127:. The algorithm takes time bounded by a polynomial in
20:, several authors have studied the computation of the
714:
708:(2006), "Simulated annealing in convex bodies and an
589:
229:
209:
173:
153:
133:
109:
89:
69:
788:
743:
618:
235:
215:
187:
159:
139:
115:
95:
75:
789:Bringmann, Karl; Friedrich, Tobias (2010-08-01).
852:
659:
449:
522:
700:
356:(1987), "Computing the volume is difficult",
83:approximation to the volume of a convex body
534:, New York, NY, USA: ACM, pp. 156–163,
348:
403:
806:
766:
539:
476:
381:
371:
326:
247:over these cubes. By using the theory of
754:Journal of Computer and System Sciences
853:
307:
266:This work earned its authors the 1991
36:. It is known that, in this model, no
626:volume algorithm for convex bodies",
445:
443:
195:. The algorithm combines two ideas:
58:polynomial time approximation scheme
359:Discrete and Computational Geometry
314:Discrete and Computational Geometry
13:
669:Random Structures & Algorithms
628:Random Structures & Algorithms
565:
440:
282:
14:
877:
694:
653:
516:
397:
342:
301:
223:by placing a grid consisting of
782:
273:
243:-dimensional cubes and doing a
825:11858/00-001M-0000-000F-1603-4
738:
725:
613:
600:
500:
188:{\displaystyle 1/\varepsilon }
1:
583:(1997), "Random walks and an
511:American Mathematical Society
294:
817:10.1016/j.comgeo.2010.03.004
744:{\displaystyle O^{*}(n^{4})}
619:{\displaystyle O^{*}(n^{5})}
249:rapidly mixing Markov chains
76:{\displaystyle \varepsilon }
7:
44:. However, a joint work by
10:
882:
768:10.1016/j.jcss.2005.08.004
414:SIAM Journal on Computing
30:combinatorial enumeration
866:Approximation algorithms
201:Markov chain Monte Carlo
513:, retrieved 2017-08-03.
507:Fulkerson Prize winners
38:deterministic algorithm
861:Computational geometry
795:Computational Geometry
745:
681:10.1002/rsa.3240040402
620:
289:Klee's measure problem
237:
217:
189:
161:
141:
117:
97:
77:
56:provided a randomized
18:analysis of algorithms
746:
621:
541:10.1145/103418.103439
478:10.1145/102782.102783
238:
218:
190:
162:
142:
118:
98:
78:
712:
587:
227:
207:
171:
151:
131:
107:
87:
67:
24:of high-dimensional
751:volume algorithm",
147:, the dimension of
741:
616:
581:Simonovits, MiklĂłs
464:Journal of the ACM
373:10.1007/BF02187886
328:10.1007/BF02187701
256:rejection sampling
233:
213:
185:
157:
137:
113:
93:
73:
551:978-0-89791-397-3
236:{\displaystyle n}
216:{\displaystyle K}
160:{\displaystyle K}
140:{\displaystyle n}
116:{\displaystyle n}
96:{\displaystyle K}
873:
845:
844:
810:
786:
780:
779:
770:
750:
748:
747:
742:
737:
736:
724:
723:
706:Vempala, Santosh
698:
692:
691:
657:
651:
650:
625:
623:
622:
617:
612:
611:
599:
598:
569:
563:
562:
543:
524:Applegate, David
520:
514:
504:
498:
497:
480:
447:
438:
437:
401:
395:
394:
385:
375:
346:
340:
339:
330:
305:
242:
240:
239:
234:
222:
220:
219:
214:
194:
192:
191:
186:
181:
166:
164:
163:
158:
146:
144:
143:
138:
122:
120:
119:
114:
102:
100:
99:
94:
82:
80:
79:
74:
54:Ravindran Kannan
881:
880:
876:
875:
874:
872:
871:
870:
851:
850:
849:
848:
787:
783:
732:
728:
719:
715:
713:
710:
709:
699:
695:
658:
654:
607:
603:
594:
590:
588:
585:
584:
570:
566:
552:
521:
517:
505:
501:
448:
441:
427:10.1137/0217060
402:
398:
347:
343:
306:
302:
297:
285:
283:Generalizations
276:
268:Fulkerson Prize
263:original body.
228:
225:
224:
208:
205:
204:
177:
172:
169:
168:
152:
149:
148:
132:
129:
128:
108:
105:
104:
88:
85:
84:
68:
65:
64:
34:convex polytope
12:
11:
5:
879:
869:
868:
863:
847:
846:
801:(6): 601–610.
781:
761:(2): 392–417,
740:
735:
731:
727:
722:
718:
693:
675:(4): 359–412,
665:Simonovits, M.
652:
615:
610:
606:
602:
597:
593:
577:Lovász, László
564:
550:
515:
499:
439:
421:(5): 967–974,
396:
366:(4): 319–326,
354:Füredi, Zoltán
341:
321:(4): 289–292,
299:
298:
296:
293:
284:
281:
275:
272:
260:
259:
252:
232:
212:
184:
180:
176:
156:
136:
112:
92:
72:
50:Alan M. Frieze
9:
6:
4:
3:
2:
878:
867:
864:
862:
859:
858:
856:
842:
838:
834:
830:
826:
822:
818:
814:
809:
804:
800:
796:
792:
785:
778:
774:
769:
764:
760:
756:
755:
733:
729:
720:
716:
707:
703:
697:
690:
686:
682:
678:
674:
670:
666:
662:
656:
649:
645:
641:
637:
633:
629:
608:
604:
595:
591:
582:
578:
574:
568:
561:
557:
553:
547:
542:
537:
533:
529:
525:
519:
512:
508:
503:
496:
492:
488:
484:
479:
474:
470:
466:
465:
460:
456:
452:
446:
444:
436:
432:
428:
424:
420:
416:
415:
410:
406:
400:
393:
389:
384:
379:
374:
369:
365:
361:
360:
355:
351:
345:
338:
334:
329:
324:
320:
316:
315:
310:
304:
300:
292:
290:
280:
271:
269:
264:
257:
253:
250:
246:
230:
210:
202:
198:
197:
196:
182:
178:
174:
154:
134:
126:
110:
90:
70:
61:
59:
55:
51:
47:
43:
39:
35:
31:
27:
26:convex bodies
23:
19:
798:
794:
784:
758:
752:
696:
672:
668:
655:
631:
627:
573:Kannan, Ravi
567:
531:
528:Kannan, Ravi
518:
502:
468:
462:
459:Kannan, Ravi
455:Frieze, Alan
451:Dyer, Martin
418:
412:
409:Frieze, Alan
405:Dyer, Martin
399:
363:
357:
350:Bárány, Imre
344:
318:
312:
303:
286:
277:
274:Improvements
265:
261:
62:
15:
634:(1): 1–50,
471:(1): 1–17,
245:random walk
199:By using a
46:Martin Dyer
855:Categories
702:Lovász, L.
661:Lovász, L.
309:Elekes, G.
295:References
833:0925-7721
808:0809.0835
721:∗
596:∗
383:1813/8572
254:By using
183:ε
71:ε
560:15432190
495:13268711
841:5930593
777:2205290
689:1238906
648:1608200
487:1095916
435:0961051
392:0911186
337:0866364
42:#P-hard
16:In the
839:
831:
775:
687:
646:
558:
548:
493:
485:
433:
390:
335:
125:oracle
22:volume
837:S2CID
803:arXiv
556:S2CID
491:S2CID
829:ISSN
546:ISBN
167:and
52:and
821:hdl
813:doi
763:doi
677:doi
636:doi
536:doi
473:doi
423:doi
378:hdl
368:doi
323:doi
103:in
857::
835:.
827:.
819:.
811:.
799:43
797:.
793:.
773:MR
771:,
759:72
757:,
704:;
685:MR
683:,
671:,
663:;
644:MR
642:,
632:11
630:,
579:;
575:;
554:,
544:,
526:;
509:,
489:,
483:MR
481:,
469:38
467:,
457:;
453:;
442:^
431:MR
429:,
419:17
417:,
407:;
388:MR
386:,
376:,
362:,
352:;
333:MR
331:,
317:,
291:.
270:.
48:,
843:.
823::
815::
805::
765::
739:)
734:4
730:n
726:(
717:O
679::
673:4
638::
614:)
609:5
605:n
601:(
592:O
538::
475::
425::
380::
370::
364:2
325::
319:1
231:n
211:K
179:/
175:1
155:K
135:n
111:n
91:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.