<p>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 </p>

<p>$$ B \subset TK  \tilde{\subset}\  \sigma B$$</p>

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

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

<p>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.</p>

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

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

CC BY-SA 3.0
2013-02-20T16:48:54.897Z
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
CC BY-SA 3.0
2013-02-20T16:58:28.317Z
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: http://www.jstor.org/discover/10.2307/3690235?uid=3739832&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21101678846583. 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
CC BY-SA 3.0
2013-02-20T17:59:38.110Z
I should have clarified: the result holds "ignoring a tiny fraction of K". I've updated the question.
Suresh Venkat
CC BY-SA 3.0
2013-02-20T19:24:26.457Z
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
CC BY-SA 3.0
2013-02-20T19:43:06.993Z
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
CC BY-SA 3.0
2013-02-20T23:20:16.607Z
Yes :). that's exactly right.
Suresh Venkat
CC BY-SA 3.0
2013-02-22T07:20:45.513Z
Have you tried asking some of the authors of relevant papers?
Chandra Chekuri
CC BY-SA 3.0
2013-02-22T17:43:14.250Z
Not yet. there are some papers (one by Lovasz and Deak for example) that discuss the empirical behavior of some of the methods, but the overall message is "everything kind of works but is terrible in practice".
Suresh Venkat
<cg.comp-geom><randomized-algorithms><convex-geometry>
On preprocessing a convex polyhedron prior to sampling
Suresh Venkat
# On preprocessing a convex polyhedron prior to sampling

(Asked by: username_0 on 2013-02-20)

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

**Tags:** cg.comp-geom, randomized-algorithms, convex-geometry
> **Comments:**
> **username_1**: 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$.  
> **username_1**: 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: http://www.jstor.org/discover/10.2307/3690235?uid=3739832&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21101678846583. 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.  
> **username_0**: I should have clarified: the result holds "ignoring a tiny fraction of K". I've updated the question.  
> **username_1**: 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?  
> **username_1**: 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?  
> **username_0**: Yes :). that's exactly right.  
> **username_2**: Have you tried asking some of the authors of relevant papers?  
> **username_0**: Not yet. there are some papers (one by Lovasz and Deak for example) that discuss the empirical behavior of some of the methods, but the overall message is "everything kind of works but is terrible in practice".  

---

## 0 answers

