Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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$ ?

share|improve this question
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$. –  Sasho Nikolov Feb 20 '13 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. –  Sasho Nikolov Feb 20 '13 at 16:58
I should have clarified: the result holds "ignoring a tiny fraction of K". I've updated the question. –  Suresh Venkat Feb 20 '13 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? –  Sasho Nikolov Feb 20 '13 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? –  Sasho Nikolov Feb 20 '13 at 19:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.