8
$\begingroup$

Given a convex body $K\in\mathbb{R}^n$, represented by a set of linear inequalities (intersection of halfspaces), I am interested in understanding how much of its volume can be close to its perimeter (under certain restrictions).

More formally, given a parameter $k$, and a partition of $\mathbb{R}^n$ into boxes of side $k$, I would like to know how large can the ratio $|P|/|I|$ be, where $P$ is the set of such boxes which intersect the perimeter, and $I$ is the set of boxes fully contained in $K$ (such a bound would be important for determining the accuracy of integration, for example).

I believe that as in 2 and 3 dimensions, the smallest ratio would be achieved by a ball (sphere), and that the worst ratio would be achieved for polytopes whose volume approaches 0 (by having a width smaller than k in one dimension, for example, which gives $|I|=0$).

However - are there some reasonable limits (for example, containing the 1/n unit sphere, or just having a volume > 0, and a poly(n) representation length of the linear inequalities) that can determine an upper bound on this ratio?

Many thanks, Guy

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Is $k$ fixed? Otherwise, it seems that I can make $|P|/|I|$ as large or small as I want: to make it small, take $K$ a $(M+\1/2)k \times (M+\1/2)k \times \dots \times (M+1/2)k$ box positioned correctly, so that $M^n$ boxes lie inside, and then because there are $2^n$ faces to the cube, there are $M^{n-1}$ cubes on each face. Thus $|P|/|I| = 2^n M^{n-1}/M^n= 2^n/M$, so for large $M$, this goes to $0$. On the other hand, you can take an $(Mk)^{n-1}\times (1/2)k$ box, and then all of the boxes intersect the boundary, so your ratio is undefined. $\endgroup$
    – Otis Chodosh
    Commented Oct 28, 2011 at 16:23
  • $\begingroup$ Perhaps I mean, "if $k$ is fixed" then ... I assume you should either let $k\to 0$, or give some further conditions on your convex set $K$. $\endgroup$
    – Otis Chodosh
    Commented Oct 28, 2011 at 16:24
  • 1
    $\begingroup$ In terms of lower bound sphere is not optimal; say in 2D a square is a better choice. There is an upper bound in terms of $k$, diameter and volume. Is that what you want? $\endgroup$
    – Anton Petrunin
    Commented Oct 29, 2011 at 3:05

1 Answer 1

Reset to default
2
$\begingroup$

A few updates to the question:

  1. Thanks for the correction about the minimality of a square (I was thinking of surface area/volume ratio, which is similar but different).

  2. $k$ is not a fixed parameter, but can vary with a given $K$. However, I cannot just let $k\rightarrow 0$, since I am thinking about an algorithm which is limited in space (and running time), and would like to understand how small does $k$ need to be in order to guarantee that the above ratio $|P|/|I|$ is not too bad (for example, that it is $\leq 1$).

So - to rephrase the above question: Let's assume that $K$ is a polytope in $\mathbb{R}^n$, and that it has a representation using poly(n) bits, as a set of linear inequalities. We also assume that it has volume greater than 0 (easy to verify). If it is helpful, we may even assume that it contains the $\frac{1}{n}$ sphere in $\mathbb{R}^n$.

How small should the parameter $k$ (determining how fine we integrate) be, to determine that $|P|/|I|\leq 1$ ?

Thanks again, Guy

Improve this answer
$\endgroup$
5
  • $\begingroup$ My instinct would be to work from the boundary-volume ratio of the polytope. If the boundary/volume ratio of the polytope is $r$, then an easy argument shows that $|P|/|I|>2r\sqrt{n}k/(1-r\sqrt{nk})$, so you just need $k<1/(3r\sqrt{n})$. This bound should be tight to an approximately constant factor. The reason for this is that $|P|$ is proportional to surface area over $k/^2$, and $|P+I|$ is proportional to volume over $k^3$. I believe you can derive a bound on $r$ from the sphere-inclusion. The worst-case should be two very thin, very long cones glued together. $\endgroup$
    – Will Sawin
    Commented Oct 30, 2011 at 17:38
  • $\begingroup$ poly(n) bits is not very helpful at all, I don't think. Consider the equations $0\leq x_1\leq 1$, $0\leq x_2 \leq 1$, ... $0\leq x_{n-1}\leq 1$. Finite number of bits. $0\leq x_n \leq \epsilon$, $\log \epsilon$ bits. Clearly for this polytope you need $k<\epsilon$, so $k<2^{-poly(n)}$. Presumably a bound that bad is not acceptable. $\endgroup$
    – Will Sawin
    Commented Oct 30, 2011 at 18:09
  • $\begingroup$ @Will: 1) I didn't understand your first comment: why are $|P|$ and $|P+I|$ proportional as you say? For example, if you take a very "jagged" boundary, you will not necessarily increase $|P|$, but will increase the surface area by a great deal. 2) A box with a side with a polynomial length representation is sufficient for approximate integration in polynomial time (at least as far as I understand) - so that's not a problem. $\endgroup$
    – Guy Adini
    Commented Oct 31, 2011 at 19:04
  • $\begingroup$ Sorry, I meant to give an upper bound for $|P|/|I|$, not a lower bound. The area could get quite large without intersecting a bunch of boxes, but it can't intersect a bunch of boxes without being large. Approximate integration isn't really what we're doing here. This is one specific trick for approximate integration. There are others that can work when this doesn't. $\endgroup$
    – Will Sawin
    Commented Jun 25, 2012 at 4:55
  • 2
    $\begingroup$ You should edit your question rather than letting this as an answer. $\endgroup$
    – Benoît Kloeckner
    Commented Aug 20, 2012 at 11:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .