40
$\begingroup$

For every convex compact set $K$ of area $1$ in $\mathbb{R}^2$, among all ellipses of area $1$ there exists an ellipse $E$ such that the area of the symmetric difference between $K$ and $E$ is smallest possible.

Questions.

(a) Is $E$ unique?

(b) If the answer is "yes", does the same hold for the analogous question in higher dimensions?

$\endgroup$
  • 2
    $\begingroup$ @T.Amdeberhan: A compact convex set of area $1$ is necessarily a convex disk (a convex $2$-dmensional body). It is known that each of, the maximum-area ellipsoid contained in a convex body $K$ in $\mathbb{R}^n$ and the minimum-area ellipsoid containing $K$ is unique. $\endgroup$ – Wlodek Kuperberg Dec 22 '16 at 22:02
  • 2
    $\begingroup$ The first sentence follows from a standard compactness argument. Disk is also used to denote any, typically convex set. $\endgroup$ – domotorp Dec 22 '16 at 22:03
  • 2
    $\begingroup$ I can imagine (but not readily prove) that there are three non circular ellipses which might serve for a truncated modification of an equilateral triangle (or perhaps no modification is needed). Can you prove that a circle would be minimal? Gerhard "Not Seeing The Numbers Yet" Paseman, 2016.12.22. $\endgroup$ – Gerhard Paseman Dec 22 '16 at 22:12
  • 3
    $\begingroup$ Besides the John-ellipsoid, I wonder if the Milman-ellipsoid is relevant? I can only find this PNAS paper on the M-ellipsoid: "An M-ellipsoid $E$ of a convex body $K$ has small covering numbers with respect to $K$." $\endgroup$ – Joseph O'Rourke Dec 22 '16 at 23:19
  • 2
    $\begingroup$ @JosephO'Rourke: The pair of "Banach-Mazur" homothetic ellipsoids is relevant, too, one contained in-, the other containing $K$, with the minimum homothety coefficient -- as in the definition of the Banach-Mazur metric. But uniqueness of the pair fails already in dimension 3, even for centrally symmetric $K$. $\endgroup$ – Wlodek Kuperberg Dec 23 '16 at 1:21
5
$\begingroup$

Question (a) has a positive answer in the centrally symmetric case. The proof is involved and I will only summarize the strategy here. Full details can be found in this ArXiv paper. Comments, suggestions, corrections etc are welcome.

Let $K \subset \mathbb{R}^2$ be a compact convex set of area $\pi$. To prove uniqueness of best ellipse approximation, it is sufficient to consider ellipses in the family $E_t := \{(x,y) \in \mathbb{R}^2 ; e^t x^2 + e^{-t} y^2 \le 1 \}$ (because any pair of ellipses can be put inside the family by applying a suitable area-preserving linear map). I actually show that the function $A(t) := \mathrm{area} (K \vartriangle E_t)$ has a unique minimum, and is strictly decreasing (resp. increasing) to the left (resp. right) of it. Equivalently, the function is "strictly quasiconvex".

First, I consider where $K$ is regular: this means that that $K$ has a smooth boundary which is transverse to all ellipses $\partial E_t$, except for a finite number of non-degenerate (i.e. quadratic) tangencies, all of which occur outside the envelope hyperbola $xy = \pm 1/2$. In this regular case, I prove the following more precise "uniform quasiconvexity" properties:

  • The function $A$ is $C^1$ everywhere and $C^2$ except at the tangency parameters.

  • If $t$ is not a tangency parameter, then: $$ \max\{|A'(t)|, A''(t)\} > \delta(A(t)) > 0, \tag{$\star$} $$ where $\delta$ is some positive continuous function on the interval $(0,2\pi)$ that does not depend on $K$.

It's not difficult to convince oneself that these properties imply the strict quasiconvexity of the function $A$. Actually any uniform limit of functions with the properties above is also strictly quasiconvex.

Finally, an arbitrary $K$ can always be perturbed with respect to the symmetric difference metric so that it becomes regular. So it follows that the function $A$ is always strictly quasi-convex.

How are the quasiconvexity properties proved (in the regular case)?

By applying a suitable linear map, it is sufficient to consider $t=0$. Suppose this is not a tangency parameter (as the case of tangency is actually easier). Similarly to my older "answer", one can deduce formulas for the derivatives $A'(0)$ and $A''(0)$. Actually $A'(0)$ depends only on the points of intersection between $\partial K$ and the unit circle $\partial E_0$, while $A''(0)$ depends also on the angles of intersection. An inspection of the second formula shows that $A''(0)$ has a strong "tendency" for being positive; for example if no two consecutive intersection points are separated by an angle $>\pi/2$ then $A''(0)>0$. What we need to show in order to obtain the main inequality $(\star)$ is that if $A''(0) \leq 0$ (and $A(0)$ is not too close to $0$ or $2\pi$) then $A'(0)$ cannot be too close to zero. This is done by a case-by-case analysis, combining analytic and geometric arguments -- I can only refer to the paper for the details.

UPDATE (May 2018): The assumption that the ellipses have exactly the same area as $K$ is never used; actually if we consider ellipses whose area is a number $\lambda$ between the areas of the John and the Loewner ellipses of $K$ then the analogous uniqueness theorem holds. So I ultimately obtain a positive answer in dimension $2$ for a question of Artstein-Avidan and Katzin about uniqueness of "maximal intersection ellipsoids".

| cite | improve this answer | |
$\endgroup$
11
$\begingroup$

Not an answer, just an illustration to accompany the question. $K$ is an isosceles triangle with base $2$ and altitude $3$ (and so area $3$). First, I mistakenly computed the ellipse $E$ of any area with the smallest area symmetric difference with $K$. It has area about $2.4$:


            SymDiff13not
After Gerhard's comment, I recomputed constraining $E$ to have area $3$. Then its center is $(0,1)$ and its axes are roughly $0.74$ and $1.29$:
            SymDiff13area3


| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Nice graphics, thanks! The points of intersection of the ellipse and the triangle are the vertices of an affine-regular hexagon. $\endgroup$ – Wlodek Kuperberg Dec 23 '16 at 1:29
  • 1
    $\begingroup$ @WlodekKuperberg: "affine-regular hexagon": That's beautiful! I added the hexagon. $\endgroup$ – Joseph O'Rourke Dec 23 '16 at 1:40
  • 2
    $\begingroup$ It looks like your K and E do not have the same area (E seems to have smaller area). Is it possible to post another picture in which K and E do have the same area? Gerhard "In Line With The Post" Paseman, 2016.12.22. $\endgroup$ – Gerhard Paseman Dec 23 '16 at 2:33
  • 6
    $\begingroup$ The problem is invariant under area-preserving affine maps, so it is sufficient to consider equilateral triangles. $\endgroup$ – Jairo Bochi Dec 23 '16 at 12:49
  • 2
    $\begingroup$ Assuming the optimal ellipse meets transversally the boundary of $K$ in $n$ consecutive arcs with endpoints $z_{2k}, z_{2k+1}$, the points $z_k$ being in cyclic order, I think the following hold (in complex notation) $$\sum_{k=1}^{2n}(-1)^k z_k=0$$ $$\sum_{k=1}^{2n}(-1)^k z_k^2=0$$ $\endgroup$ – Pietro Majer Dec 24 '16 at 13:13
7
$\begingroup$

I don't have a proof, but I have an idea which suggests the answer is no, the minimal ellipse may not be unique. Right or wrong, I hope someone will generate a picture to illustrate the idea, and see if in addition there is a near-octagon which exhibits the pair of minimal ellipses.

I use eight-fold symmetry and restrict attention to the positive quadrant. Draw a quarter circle of unit radius, a nearly circular ellipse quarter with major axis $1+ \epsilon$ and minor axis $1/(1+\epsilon)$, and a reflection about $x=y$ of this quarter ellipse. (The ellipses axes lie on the axes bordering the quadrant.) Consider the point of intersection $P$ between the ellipses and the line x=y. One vertex of the proposed octagon will be $P$, and another will be the point $Q=(0, 1+ \epsilon)$. There will be a curve between the two which bisects that portion of the symmetric difference between the two ellipses.

I challenge the illustrator to find a curve which does such an area bisection, and induces a near octagon which does not have a smaller symmetric difference with the unit circle. I believe it possible because 1) the point $P$ is far enough in the interior of the circle that much of the circle "sticks out", and 2) the freedom one has in bisecting the portion of the ellipse symmetric difference. This may not prove that the given ellipses are minimal, but it may be possible to draw the curve to show that any minimal ellipse must have a reflection which is also minimal.

Gerhard "Easily Writes One Thousand Words..." Paseman, 2016.12.23


    GPOct
    Figure added by J.O'Rourke. $\epsilon=\frac{1}{10}$.


    Rounded octagon
    Figure added by Jairo Bochi.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Joseph! Unfortunately, it looks like P is very close to the circle, so more care will be needed to form the octaoscilliptical disk. Gerhard "And Merry Christmas To All" Paseman, 2016.12.24. $\endgroup$ – Gerhard Paseman Dec 24 '16 at 16:42
  • 1
    $\begingroup$ I included a figure with a candidate set. It's not exactly your suggestion since P is not a boundary point, but it seems to be more efficient. Still, it's not sufficient to beat the circle (even taking smaller epsilon's). $\endgroup$ – Jairo Bochi Dec 24 '16 at 17:20
  • $\begingroup$ "it looks like $P$ is very close to the circle": Indeed my drawing was slightly inaccurate; fixed now. Jairo's shows the situation more clearly. $\endgroup$ – Joseph O'Rourke Dec 24 '16 at 20:00
  • $\begingroup$ I also initially thought that the are of the circle that "sticks out" might be the key for a counterexample. But that area is too small, unless epsilon is big (in which case the circle seems even more unbeatable). $\endgroup$ – Jairo Bochi Dec 24 '16 at 20:55
  • 2
    $\begingroup$ I added labels to the figure. In order that the set with black boundary (which has the required area) be a counterexample (i.e., to be closer to the ellipses than to the circle), we would need the following inequality between areas: a+b+c>d+e. It should be clear now that there is no advantage in having P in the boundary of the set; actually the set in the figure seems to be the optimal choice. Still, the inequality fails to hold for all choices of epsilon, if my calculations are correct. I can't imagine a better attempt, so I suspect that no counterexample exists. Happy holidays! $\endgroup$ – Jairo Bochi Dec 24 '16 at 22:22
5
$\begingroup$

Now the answer is almost complete: modulo some extra work on the strictness of relevant inequalities, we do have the uniqueness. The additional ideas used to come to this conclusion are these: (i) to kind of reduce approximating a convex set by an ellipse by, vice versa, approximating an ellipse (and even a round disk) by shear-shifted versions of the convex set; (ii) shear-symmetrization; and
(iii) minimizing the symmetric difference given the same areas is equivalent to maximizing the area of the intersection (the latter observation borrowed from Matt F.).

How to show that the best possible ellipse is unique?
Suppose that $E_1$ and $E_2$ are distinct best possible ellipses. By an appropriate rescaling of everything in the directions of principal axes of $E_1$, without loss of generality (wlog) $E_1$ is a round disk, say $D$, of radius $1/\sqrt\pi$.

Then the width of $E_2$ in some direction is the same as that of the round disk $E_1$ (that is, $2/\sqrt\pi$), where the width of a set in a given direction is defined as the width of the narrowest infinite band that contains the set and goes in the direction perpendicular to the given one. This follows because the product of the widths of ellipse $E_2$ in the directions of its principal axes is $(2/\sqrt\pi)^2$.

So, there exist the following: (i) a real $t$; (ii) a vector $b\in\mathbb{R}^2$; and (iii) an orthonormal basis $(e_1,e_2)$ of $\mathbb{R}^2$ such that, for the (shear-shift) affine operator $A=A_t=A_{b,t}$ on $\mathbb{R}^2$ defined by the conditions $A\mathbf0=b$, $Ae_1=b+e_1$, and $Ae_2=b+e_2+te_1$, we have $AE_1=AD=E_2$.

Let then $E_0:=\dfrac{I+A}2\,D$, where $I$ is the identity operator. Then $E_0$ is an ellipse of area $1$.

For real $y$, let $[u,v]=[u(y),v(y)]=K_y:=K(y):=\{x\in\mathbb R\colon xe_1+ye_2\in K\}$ be the $y$-"cross-section" of $K$. Similarly define the $y$-"cross-sections" $E_1(y)=[r_1,s_1]$ and $E_2(y)=[r_2,s_2]$ of $E_1$ and $E_2$. Then the $y$-"cross-section" $E_0(y)$ of $E_0$ is $[r_0,s_0]=[\frac{r_1+r_2}2,\frac{s_1+s_2}2]$. Let $|\cdot|$ denote the Lebesgue measure on $\mathbb{R}$ or $\mathbb{R}^2$. Then $|E_j\cap K|=\int_{\mathbb{R}}\delta_j(y)\,dy$ for $j=0,1,2$, where $\delta_j(y):=|E_j(y)\cap K(y)|$. So, if we could show that \begin{equation} \delta_0(y)\ge\tfrac12\,\delta_1(y)+\tfrac12\,\delta_2(y) \tag{*} \end{equation} for all $y$ and that this inequality is strict for some $y$ given that $E_1$ and $E_2$ are distinct, then we would obtain the desired contradiction: $|E_0\cap K|>\tfrac12\,|E_1\cap K|+\tfrac12\,|E_2\cap K|=|E_1\cap K|=|E_2\cap K|$. Here we have used the mentioned additional idea (iii).

Unfortunately, inequality $(*)$ does not hold in general, without any assumptions on the convex sets $E_j$. Here we need the mentioned additional ideas (i) and (ii).

Consider first the round disk $E_1=D$, which is an optimal approximation of $K$. I then claim that for all the $y$-"cross-sections" of $E_1$ and $K$ we have $\frac{r_1+s_1}2=\frac{u+v}2$. Indeed, since $D$ is an optimal approximation of $K$, it is also an optimal approximation of $K^-$, where $K^-$ is obtained from $K$ by the reflection about the diameter of $D$ parallel to $e_2$. Wlog $D$ is centered at the origin. So, for all $y$ we have $r_1=-s_1$, and the $y$-"cross-section" of $K^-$ is $K^-_y=[-v,-u]=-K_y$. Then for $K^0:=\frac12\,(K+K^-)$ we can check that $|D_y\cap K^0_y|\ge\tfrac12\,|D_y\cap K_y| +\tfrac12\,|D_y\cap K^-_y|$ for all $y$. So,
the disk $D$ approximates $K^0$ no worse than it does $K$ (or $K^-$). Extra work is needed here to show that $D$ approximates $K^0$ (strictly) better than it does $K$ (or $K^-$) unless $K^-=K$.

But $K^0$ is the image of $K$ under an (area-preserving) shear-shift transformation (say $B$). So, modulo the mentioned extra work, we will conclude that $B^{-1}E_1=B^{-1}D$ is a better (than $D$) approximation of $K$ -- unless $K^-=K$. So, wlog $K^-=K$, which verifies the claim $\frac{r_1+s_1}2=\frac{u+v}2$. Similarly, by shear-shifting, $\frac{r_2+s_2}2=\frac{u+v}2$. Given these two conditions, one can verify that $(*)$ holds (in that verification, wlog $\frac{r_1+s_1}2=\frac{r_2+s_2}2=\frac{u+v}2=0$). It will remain to show that inequality $(*)$ will be strict for some $y$ unless $E_1=E_2$.

For readers' convenience(?), I am retaining below, under the horizontal line, the previous version of the answer.


This is not a complete answer, but I think it has a chance to lead to one.

I think the best possible ellipse is unique. Suppose that $E_1$ and $E_2$ are distinct best possible ellipses. By an appropriate rescaling of everything in the directions of principal axes of $E_1$, without loss of generality $E_1$ is a round disk, say $D$, of radius $1/\sqrt\pi$.

Then the width of $E_2$ in some direction is the same as that of the round disk $E_1$ (that is, $2/\sqrt\pi$), where the width of a set in a given direction is defined as the width of the narrowest infinite band that contains the set and goes in the direction perpendicular to the given one. This follows because the product of the widths of ellipse $E_2$ in the directions of its principal axes is $(2/\sqrt\pi)^2$.

So, there exist the following: (i) a real $t$; (ii) a vector $b\in\mathbb{R}^2$; (iii) an orthonormal basis $(e_1,e_2)$ of $\mathbb{R}^2$; and (iv) a (shearing) affine operator $A$ on $\mathbb{R}^2$ such that $Ae_1=b+e_1$, $Ae_2=b+e_2+te_1$, and $AE_1=AD=E_2$.

Let then $E_0:=\dfrac{I+A}2\,D$, where $I$ is the identity operator. Then $E_0$ is an ellipse of area $1$.

For real $y$, let $[u,v]=[u(y),v(y)]=K(y):=\{x\in\mathbb R\colon xe_1+ye_2\in K\}$ be the $y$-"cross-section" of $K$. Similarly define the $y$-"cross-sections" $E_1(y)=[r_1,s_1]$ and $E_2(y)=[r_2,s_2]$ of $E_1$ and $E_2$. Then the $y$-"cross-section" $E_0(y)$ of $E_0$ is $[r_0,s_0]=[\frac{r_1+r_2}2,\frac{s_1+s_2}2]$. Let $\oplus$ denote the symmetric difference, and let $|\cdot|$ denote the Lebesgue measure on $\mathbb{R}$ or $\mathbb{R}^2$. Then $|E_j\oplus K|=\int_{\mathbb{R}}\delta_j(y)\,dy$ for $j=0,1,2$, where $\delta_j(y):=|E_j(y)\oplus K(y)|$. So, if we could show that \begin{equation} \delta_0(y)\le\tfrac12\,\delta_1(y)+\tfrac12\,\delta_2(y) \tag{*} \end{equation} and this inequality is strict for some $y$ given that $E_1$ and $E_2$ are distinct, then we would obtain the desired contradiction: $|E_0\oplus K|<\tfrac12\,|E_1\oplus K|+\tfrac12\,|E_2\oplus K|=|E_1\oplus K|=|E_2\oplus K|$.

Unfortunately, inequality $(*)$ does not hold in general, without any assumptions on the convex sets $E_j$. However, it will hold for all real $y$ such that $E_j(y)\cap K(y)\ne\emptyset\ \forall j\in\{1,2\}$ or $K(y)=\emptyset$.

Anyway, we need $(*)$ to hold on the average, given that both ellipses $E_1=D$ and $E_2$ are optimal approximations of $K$; this "average" inequality seems likely.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Now the answer is almost complete: modulo some extra work on the strictness of relevant inequalities, we do have the uniqueness. $\endgroup$ – Iosif Pinelis Jan 5 '17 at 12:24
  • $\begingroup$ This would make a nice paper! $\endgroup$ – Joseph O'Rourke Jan 5 '17 at 13:37
  • $\begingroup$ Thank you Joseph. Still some work on the strictness of the inequalities remains. $\endgroup$ – Iosif Pinelis Jan 5 '17 at 13:43
  • 1
    $\begingroup$ Alas, there is a mistake in the latest version of the answer: in general, of course $B$ will not be a shear-shift transformation. Still, I am leaving the answer as it is, hoping that some of the ideas there could prove useful. $\endgroup$ – Iosif Pinelis Jan 5 '17 at 15:10
3
+200
$\begingroup$

Update: I previously claimed that I had a negative answer to question (a) in the centrally symmetric case, but thanks to Matt F. I found that there was an error in my calculation. I corrected the calculation, so what follows is not an answer but just a case study.


I'll consider the modified version of the problem where all sets are centrally symmetric (i.e., $K=-K$, $E=-E$). I'll normalize all areas to $\pi$ instead of $1$.

Let $\varepsilon$ be a parameter in the interval $(0,1)$. Let $K_\varepsilon$ be the topological disk bounded by the Jordan curve given in polar coordinates by: $$ r^2 = 1 + \varepsilon \cos 4 \theta . $$ The figure shows the case $\varepsilon = 1/9$: my convex set

Obviously, $K_\varepsilon$ has area $\int_0^{2\pi} \frac{1}{2} r^2 d\theta = \pi$, and it is convex for $\varepsilon$ sufficiently close to $0$.

Note that $K_\varepsilon$ is invariant under $R_{\pi/2}$ (the rotation of $\pi/2$). Therefore if $E$ is a minimizing ellipse, so is $R_{\pi/2}(E)$. So, to prove that the minimizing ellipse is not unique, it is sufficient to show that the unit disk is not a minimizer.

Let $t$ be a real parameter and let $E_t$ be the ellipse with boundary $e^{t} x^2 + e^{-t}y^2 = 1$, or in polar coordinates $$ r^2 = \frac{1}{e^t \cos^2\theta + e^{-t} \sin^2\theta} =: f(\theta,t). $$ Note that $R_{\pi/2}(E_t) = E_{-t}$, and so the function $A(t) := \mathrm{area}(K_\varepsilon \vartriangle E_t)$ is even.

Let $g(\theta):= 1+\varepsilon \cos 4\theta$ and $h(\theta,t) := f(\theta,t) - g(\theta)$. For $t$ sufficiently close to zero, the function $\theta \mapsto h(\theta,t)$ has two roots in the interval $[0,\pi/2]$, say $\alpha(t) < \beta(t)$. Then $$ A(t) = 2 \, \mathrm{area}(E_t \smallsetminus K_\varepsilon) = 2 \times 4 \int^{\beta(t)}_{\alpha(t)} \frac{1}{2} h(\theta,t) d\theta . $$ By the Leibniz integral rule, $$ \frac{1}{4} A'(t) = \int^{\beta(t)}_{\alpha(t)} h_t(\theta,t) d\theta + \underbrace{h(\beta(t),t)}_{0} \beta'(t)- \underbrace{h(\alpha(t),t)}_{0} \alpha'(t) $$ and $$ \frac{1}{4} A''(t) = \int^{\beta(t)}_{\alpha(t)} h_{tt}(\theta,t) d\theta + h_t(\beta(t),t) \beta'(t) - h_t(\alpha(t),t) \alpha'(t) . $$ Substituting $t=0$ and using the Implicit Function Theorem, $$ \frac{1}{4} A''(0) = \int_{\pi/8}^{3\pi/8} h_{tt}(\theta,0) d\theta - \frac{[h_t(3\pi/8,0)]^2}{h_\theta(3\pi/8,0)} + \frac{[h_t(\pi/8,0)]^2}{h_\theta(\pi/8,0)}. $$ Some calculations show that: $$ h_t(\theta,0) = -\cos 2\theta, \quad h_{tt}(\theta,0) = \cos 4\theta, \quad h_{\theta}(\theta,0) = - 4 \varepsilon \sin 4\theta. $$ Substituting we get: $$ \frac{1}{4} A''(0) = \int_{\pi/8}^{3\pi/8} \cos 4\theta d\theta + \frac{[1/\sqrt{2}]^2}{4\varepsilon \times 1} - \frac{[-1/\sqrt{2}]^2}{4\varepsilon \times (-1)} = -\frac{1}{2} + \frac{1}{4\varepsilon}. $$ So $A''(0) < 0$ (which would yield non-uniqueness of the minimizer ellipe) iff $\varepsilon>1/2$. However, $K_\epsilon$ is convex iff $\varepsilon \leq 1/9$, as one can easily check.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ By symmetry, any "off center" or "off axis" minimizing ellipse has distinct images which minimize. If your claim about the circle not minimizing holds I believe you have solved the original problem and (taking cylindrical versions) its higher dimensional versions. Gerhard "Congratulations On Approaching The Truth" Paseman, 2016.12.28. $\endgroup$ – Gerhard Paseman Dec 28 '16 at 19:44
  • $\begingroup$ Actually, for higher dimensions, Cavalieri's principle and spherical versions might work more easily than cylindrical versions. The analysis of the 2d case looks good. Gerhard "Happy To Have Helped Inspire" Paseman, 2016.12.28. $\endgroup$ – Gerhard Paseman Dec 28 '16 at 19:56
  • 1
    $\begingroup$ I do not see this when I check it in Mathematica: Table[{t, NIntegrate[ Abs[(1 + Cos[4 theta]/9) - 1/(Exp[t] Cos[theta]^2 + Exp[-t] Sin[theta]^2)], {theta, 0, 2 Pi}, PrecisionGoal -> 8, WorkingPrecision -> 8]}, {t, 0, 0.001, 0.0001}] gives {{0., 0.44444444}, {0.0001, 0.44444451}, {0.0002, 0.44444472}, {0.0003, 0.44444507}, {0.0004, 0.44444556}, {0.0005, 0.44444619}, {0.0006, 0.44444696}, {0.0007, 0.44444787}, {0.0008, 0.44444892}, {0.0009, 0.44445011}, {0.001, 0.44445144}}, which suggests that the circle is optimal. What accounts for the discrepancy? $\endgroup$ – Matt F. Dec 28 '16 at 20:25
  • $\begingroup$ In your calculations, did you use $g(\theta):= 1+\cos 4\theta$ as you stated (which apparently corresponds to a non-convex $K$) or $g(\theta):= 1+(1/9)\cos 4\theta$? $\endgroup$ – Iosif Pinelis Dec 28 '16 at 21:56
  • $\begingroup$ @MattF. Oh! I spotted a sign error in the last calculation. I'll recheck everything and try to find a fix. I plotted A(t) using Maple. I'll recheck that as well. $\endgroup$ – Jairo Bochi Dec 28 '16 at 21:57
3
$\begingroup$

Here is an approach via calculus of variations, with a request for assistance in that area.

Conjecture: Let $a$ and $h$ be positive. Let the circle $C$ and ellipses $D$, $E$ be defined by \begin{align} (x-2h)^2 + (y-2k)^2 &\le 1 \\ a(x-h)^2 + \frac{1}{a}(y-k)^2 &\le 1 \\ a^2x^2 + (1/a^2)y^2 &\le 1 \\ \end{align} Let $F$ be any convex figure of area $\pi$ with $|F \cap C| = |F \cap E| > 0.$

Then $|F \cap D| > |F \cap C| =|F \cap E|.$

In more geometrical terms, the equations define $D$ from $C$, $E$ by setting its center as the midpoint of the centers, its axes as the geometric means of the axes, and its orientation as the ellipse’s orientation. The conclusion is that if $F$ overlaps equally well with $C$ and $E$, then it must overlap better with $D$.

Answer to question given conjecture: Suppose that figure $F$ is a counterexample, with two most-overlapping ellipses of the same area. By an appropriate choice of coordinates, we may assume that they have equations $C$ and $E$ above. Then ellipse $D$ in the conjecture shows that neither $C$ nor $E$ was most-overlapping with $F$, contrary to hypothesis of a counterexample.

Proof idea for conjecture: These equations can be written in polar coordinates with $r_C$, $r_D$, and $r_E$ as explicit functions of $\cos(t), \sin(t), a, h, k$. Likewise the curve which bounds $F$ can be assumed to be $r=f(t)$. Then areas like $|F \cap D|$ can be written as $\frac{1}{2}\int \min(f,r_D)^2$.

So the variational problem is to find $f$ which \begin{align} &\text{maximizes }\int \min(f, r_C)^2 - \min(f, r_D)^2 \\ &\text{subject to }\int f^2 = 2 \pi, \\ &\text{subject to }\int \min(f, r_C)^2 - \min(f, r_E)^2 = 0, \\ &\text{subject to }f^2 + 2f’^2 – f f’’ \ge 0\text{ or a generalization for non-smooth }f.\\ \end{align} The inequality, which captures the convexity of $F$, is not integrated and should hold for all $t$.

The conjecture could be proved by showing that a maximal $f$ exists and satisfies the inequality $$\int \min(f, r_C)^2 - \min(f, r_D)^2 < 0.$$

However, the derivative of a minimum is hard to use in the calculus of variations. A close approximation is showing that for all sufficiently negative $n$, the above holds with $\min(f,r)$ replaced by $(f^n+r^n)^{1/n}$. If anyone can formulate appropriate Euler-Lagrange equations which capture the constraints, I'll search the numerical solutions for a counterexample with finite $n$ or a good limit as $n \rightarrow -\infty$.

Solving this variational problem should yield one function $f$ for each quadruple $(a,h,k,n)$. If there is a counterexample, then there should be a counterexample with smooth $f$ and finite $n$.

So this approach may improve on the initial presentation of the problem, which looked like sampling over all convex bodies, and trying to determine their intersections with various ellipses. This approach avoids that, reducing the search space to 4 dimensions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why the geometric means? Is there any reason to believe that they are what is needed? $\endgroup$ – Iosif Pinelis Jan 4 '17 at 14:49
  • $\begingroup$ @IosifPinelis, we have an ellipse with axes (1,1) and an ellipse with axes (a, 1/a). We need an ellipse with axes (b, 1/b) to keep the area constant. What other choice of b would be reasonable? This one treats the two ellipses symmetrically: if C,D,E are of the above form with a,h,k; and C',D',E' are of the above form with a',h',k'; and E'=MC, C'=ME, then also D'=MD. I think this is the only choice with that symmetry. $\endgroup$ – Matt F. Jan 4 '17 at 15:45
  • $\begingroup$ @MattF., if it helps with computations: For every pair of ellipsoids of equal volume there exists an affine transformation under which the images of the two ellipsoids are congruent. $\endgroup$ – Wlodek Kuperberg Jan 4 '17 at 19:20
  • $\begingroup$ @WlodekKuperberg : Such an affine transformation was rather explicitly constructed in my answer. $\endgroup$ – Iosif Pinelis Jan 4 '17 at 20:32
  • 1
    $\begingroup$ @WlodekKuperberg, I never actually have to calculate those transformations, I just work in the coordinates they define $\endgroup$ – Matt F. Jan 4 '17 at 20:47

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.