4
$\begingroup$

You are given a compact convex figure in the plane, $C$.

Your goal is to transform $C$ to a different figure $C'$ with the smallest possible diameter, as long as:

  • The trasformation from $C$ to $C'$ is affine and invertible (e.g. scaling in one or more directions);
  • $C'$ contains a disc with diameter $1$.

For example:

  • If $C$ is an ellipse, you can transform it to a disc with diameter $1$.
  • If $C$ is a parallelogram, you can transform it to a square with side-length $1$ and diameter $\sqrt{2}$.
  • If $C$ is a triangle, you can transform it to an equilateral triangle with diameter $\sqrt{3}$.

An ellipse is obviously the best case; what is the worst case?

Cross-post from math.se

$\endgroup$
  • 3
    $\begingroup$ What you are trying to do (at least in the centrally symmetric case) is to compute the Banach-Mazur distance between (the equivalence class of) C and (the equivalence class of) a round disk. Google "Banach-Mazur" and "John ellipsoid" and you will find relevant information. $\endgroup$ – Jairo Bochi Mar 1 '17 at 14:45
  • $\begingroup$ @JairoBochi thanks! This Wikipedia page: en.wikipedia.org/w/… mentions an upper bound of $n$ (the number of dimensions, here 2) on the Banach-Mazur distance, which seems reasonable. But, I am not sure how this distance relates to the diameter. Also, I do not know what is the worst case. $\endgroup$ – Erel Segal-Halevi Mar 6 '17 at 9:12
1
$\begingroup$

Second version after incomplete first version, using John's theorem and some remarks thereon by Keith Ball.

==

The worst case is the triangle (as intuition predicts). A few images would be really helpful, but at the moment I don't have time for this, so let me just indicate the main arguments.

To see why the triangle is the worst case, we consider a compact convex $C$, with boundary $\delta C$.

By John's theorem we know that $C$ contains a maximal-area (inscribed) ellipse $E_C$. W.l.o.g. the center of $E_C$ is the origin $(0,0)$ (otherwise translate). Our first affine transformation (say $G$) is to downscale $C$ in the longitudinal direction of the semi-major axis of $E_C$, with factor $\frac{a}{b}$ where $a,b$ are the lengths of the semi-minor and semi-major axis of $E_C$ respectively.

We then have that $G(E_C)$ is a circle, say $M$. $M$ is the maximal-area inscribed ellipse of our transformed compactum $G(C)$. Our second affine transformation $H$ is a global scaling with a factor $\frac{1}{r}$ where $r$ is the radius of $M$.

Then $H\circ G (C)=C'$ has $H(M)$ as maximal-area inscribed ellipse, and $H(M)=M'$ is the unit circle with radius $1$.

Now we apply (Keith Ball's comments on) John's theorem, to find $m$ real numbers $c_i>0$ (for $1\leq i\leq m$) and corresponding intersection points $u_i$ of $M'$ with $\delta C'$, the boundary of $C'$, such that:

a) $\Sigma c_i\cdot u_i=0$

b) $\Sigma c_i\cdot \langle x,u_i\rangle\cdot u_i=x$ for all $x\in \mathbb{R}^2$

John's theorem actually states that the unit circle (which is $M'$) is the maximal-area inscribed ellipse of a convex $K$ if and only if $K$ has intersection points $u_i$ with the unit circle admitting real numbers $c_i>0$ such that criteria a) and b) hold.

In Keith Ball's words: Condition a) shows that the contact points do not all lie "on one side" of the unit circle, and condition b) that they do not all lie "close to a proper subspace". In other words, they are sufficiently spread out over the unit circle.

$C'$ is contained entirely within the polygon $P$ delineated by the $m$ tangent lines $l_i$ to the unit circle $M'$ in the points $u_i$ respectively (picture!). The trivial reason for this is that $C$ is convex.

The polygon $P$ also has the unit circle as maximal-area inscribed ellipse, once again by John's theorem since a) and b) also hold for $P$.

In Keith Ball's paper it is proved that any convex $K$ for which the unit circle is the maximal-area inscribed ellipse, is contained in the disc around the origin with radius $2$ ($2\cdot B_2$, globally scaled twice the unit disc).

Therefore $P$ is contained in $2\cdot B_2$. From this it follows that the triangle is the worst case, using conditions a) and b). This is elegantly proved in the final remark on page 11,12 of Keith Ball's paper, stating for dimension $n$:

If $C$ is a convex body with the Euclidean unit ball $B_n$ as maximal-volume ellipsoid, then diam$(C)\leq\sqrt{2n(n+1)}$.

$\endgroup$
  • $\begingroup$ Actually, this second version is nothing new from what Keith Ball already observed, so ... the first commenter JairoBochi was right I believe. Still, I hope to have clarified his remark now. Perhaps this version can elicit some comments, I'm quite occupied with other things but will check for reactions. $\endgroup$ – Frank'a Waaldijk Mar 12 '17 at 14:10
  • $\begingroup$ ($\star$) still needs a precise proof, but one "sees" that a polygon $P$ with angle smaller than $\frac{\pi}{3}$ is oblong, and therefore does not have a circle as maximal-area inscribed ellipse. [btw I removed my previous comments on the incorrect first version since no-one reacted anyway :-)] $\endgroup$ – Frank'a Waaldijk Mar 13 '17 at 9:42
  • $\begingroup$ Completed the details of $(\star)$, they were also to be found already in Keith Ball's paper but it took me some time to realize this. $\endgroup$ – Frank'a Waaldijk Mar 13 '17 at 13:48
  • $\begingroup$ I tried several intuitive high-school level shortcuts, but discovered a glaring incompleteness in each one. And this after having described them already as answer... Not good for my self-esteem, but so be it. Anyway, it does leave me with the feeling that for $\mathbb{R}^2$ a high-school level answer is possible (without too much coordinate calculus I mean). Also I would like to know whether for polygon P with maximal-area inscribed ellipse $S_1$ and all angles > $\frac{\pi}{3}$, diam$(P)$ is less than $2\sqrt{3}$ (as I strongly suspect). $\endgroup$ – Frank'a Waaldijk Mar 14 '17 at 17:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.