11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Feb 20 '13 at 16:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Feb 20 '13 at 16:58
  • $\begingroup$ I should have clarified: the result holds "ignoring a tiny fraction of K". I've updated the question. $\endgroup$ – Suresh Venkat Feb 20 '13 at 17:59
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Feb 20 '13 at 19:24
  • 2
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Feb 20 '13 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.