# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On Computing the Vertex Centroid of a Polyhedron

##### External Ressource

No external resources are shared

##### Fulltext (public)

0806.3456.pdf

(Preprint), 199KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elbassioni, K., & Tiwary, H. R. (2008). On Computing the Vertex Centroid of a Polyhedron. Retrieved from http://arxiv.org/abs/0806.3456.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0028-9696-3

##### Abstract

Let $\mathcal{P}$ be an $\mathcal{H}$-polytope in $\mathbb{R}^d$ with vertex
set $V$. The vertex centroid is defined as the average of the vertices in $V$.
We prove that computing the vertex centroid of an $\mathcal{H}$-polytope is
#P-hard. Moreover, we show that even just checking whether the vertex centroid
lies in a given halfspace is already #P-hard for $\mathcal{H}$-polytopes. We
also consider the problem of approximating the vertex centroid by finding a
point within an $\epsilon$ 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 \emph{any} ``sufficiently'' non-trivial (for example constant)
distance, can be used to construct a fully polynomial 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^{{1/2}-\delta}$ for any fixed constant $\delta>0$.