Complexity of Approximating the Vertex Centroid of a Polyhedron

Let \(\mathcal{P}\) be an \(\mathcal{H}\)-polytope in ℝ^d with vertex set V. The vertex centroid is defined as the average of the vertices in V. We first prove that computing the vertex centroid of an \(\mathcal{H}\)-polytope, or even just checking whether it lies in a given halfspace, are #P-hard. We also consider the problem of approximating the vertex centroid by finding a point within an ε distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an \(\mathcal{H}\)-polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to any “sufficiently” non-trivial (for example constant) distance, can be used to construct a fully polynomial-time approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of \(d^{\frac{1}{2}-\delta}\) for any fixed constant δ> 0.

Authors and Affiliations

1. Max-Planck-Institut für Informatik, Saarbrücken, Germany

   Khaled Elbassioni

2. Technische Universität Berlin Fakultät II: Institut für Mathematik, 10623, Berlin, Germany

   Hans Raj Tiwary

Editors and Affiliations

1. Dept. of Electrical and Computer Engineering, University of Hawaii, Holmes Hall 483, 2540 Dole Street, 96822, Honolulu, HI, USA

   Yingfei Dong

2. Department of Computer Science, University of Texas at Dallas, 75083, Dallas, TX, USA

   Ding-Zhu Du

3. Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA

   Oscar Ibarra

Reprints and permissions

© 2009 Springer-Verlag Berlin Heidelberg

Policies and ethics