hide
Free keywords:
Computer Science, Computational Geometry, cs.CG
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$.
