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?
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".
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$:
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
Figure added by Jairo Bochi.
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.
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$:
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.
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.
