The Nesterov rounding and perfectly centered polytopes
by
Komei Fukuda
Swiss Federal Institute of Technology, Zurich and Lausanne
Coauthors: Christophe Weibel

Recently Y. Nesterov has shown that any convex body can be rounded very rapidly by taking the Minkowski sum of itself with a properly scaled dual. More specifically, the asphericity (the ratio of the outer radius over the inner radius) reduces to at least its square root. The purpose of our study is to obtain a combinatorial counterpart of the Nesterov rounding. In particular, we determine the face lattice of the Nesterov rounding applied to perfectly centered convex polytopes. Here, we say a convex polytope perfectly centered if every nonempty face intersects with its outer normal fan. We give closed formula for special cases including perfectly centered simplices and hypercubes. Our final goal is to understand the complexity of the Minkowski sum of several convex polytopes. 

Date received: February 3, 2005