A RANDOM POLYNOMIAL-TIME ALGORITHM FOR WELL-ROUNDING CONVEX-BODIES

We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K subset of or equal to R'' an d epsilon > 0, the algorithm, with probability at least 1 - epsilon, c omputes two simplices Delta and Delta**, where Delta** is the blow up of Delta from its center by a factor of n + 3, such that Delta* subs et of or equal to K and vol(K\Delta*) less than or equal to epsilon v ol K. The running time is polynomial in 1/epsilon and L, the size of t he input K.