Approximating the centroid is hard

Abstract

Consider the problem of computing the centroid of a convex body in n-dimensional Euclidean space. We prove that if the body is a polytope given as an intersection of half-spaces, then computing the centroid exactly is #P-hard, even for order polytopes, a special case of 0-1 polytopes. We also prove that if the body is given by a membership oracle, then for any deterministic algorithm that makes a polynomial number of queries there exists a body satisfying a roundedness condition such that the output of the algorithm is outside a ball of radius sigma/100 around the centroid, where sigma^2 is the minimum eigenvalue of the inertia matrix of the body.