# On preprocessing a convex polyhedron prior to sampling

Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that

$$B \subset TK \tilde{\subset}\ \sigma B$$

where $B$ is the unit ball in $d$ dimensions, and $\sigma$ is $O(\sqrt{d})$.

(Update: the $\tilde{\subset}$ indicates that the containment is true except for an $\epsilon$-fraction of $K$)

The algorithms that I've seen for computing this transform are quite tricky. They require a bootstrap sampling process to extract a few points from inside $K$ which are then used to define the transformation.

However, the fact that such a transformation exists is folklore, and my question was:

Is there a simple algorithm (with possibly a weaker bound on $\sigma$) to compute the affine transform, given only a membership oracle for $K$ ?

• Is it really "folklore"? This follows from Fritz John's theorem. Also what you wrote is true only for symmetric $K$, I believe. For example, I think $\sigma$ is $\Theta(d)$ for the $d$-dimensional simplex. John's theorem implies $\sigma = O(d)$ for general $K$. Feb 20, 2013 at 16:48
• I don't think it answers your question, and you've probably seen it, but Khachiyan has a nicely written classical paper on rounding polytopes: jstor.org/discover/10.2307/…. His input is the vertices though. If your input is inequalities, maybe there is a way to use duality to reduce between the two cases. Feb 20, 2013 at 16:58
• I should have clarified: the result holds "ignoring a tiny fraction of K". I've updated the question. Feb 20, 2013 at 17:59
• So aren't you just looking to put $K$ in (approximately) isotropic position then? I think this is equivalent to estimating the covariance of the uniform distribution on $K$, which you can do by estimating the covariance of sufficiently many random samples from $K$. What is not good about that approach? Feb 20, 2013 at 19:24
• Ok I think I see what you're saying. You can do this approximate rounding by computing the covariance of $K$, but doing that by sampling introduces circularity, because the random walk algorithms work well for isotropic $K$. There are ways around that but they are a bit involved and you'd like something simpler? Feb 20, 2013 at 19:43