Premium
Random walks and an O *( n 5 ) volume algorithm for convex bodies
Author(s) -
Kannan Ravi,
Lovász László,
Simonovits Miklós
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199708)11:1<1::aid-rsa1>3.0.co;2-x
Subject(s) - random walk , volume (thermodynamics) , regular polygon , algorithm , computer science , mathematics , geometry , physics , statistics , quantum mechanics
Given a high dimensional convex body K ⊆ℝ n by a separation oracle, we can approximate its volume with relative error ε, using O *( n 5 ) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte‐Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K ), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 1–50, 1997