Finding the largest ellipse that will fit in a polygon

[aheight]

Summary:: Questions about finding largest ellipse in polygon

Was wondering if someone could help me understand two concepts involved with finding largest ellipse in a polygon? Some background:

First, I set up a set of half-plane representations for the example polygon below and as you can see my ellipse is not fitting too well in the polygon:
$$
\mathcal{P}=\begin{cases}
\begin{aligned}
-x+y&\leq 5/2 \\
-1/6x+y&\leq 5/6 \\
2 x+y&\leq 3 \\
-1/10x-y&\leq 4/5
\end{aligned}
\end{cases}
$$
or in matrix form:
$$
\begin{bmatrix}
-1 & 1 \\
-1/6 & 1\\
2 & 1 \\
-1/10& -1
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix}
\leq
\begin{bmatrix}
5/2 \\
5/6 \\
3 \\
4/5
\end{bmatrix}
$$
or
$$\textbf{Ax}\leq\textbf{b}
$$
Next, I represent the ellipse with an affine transformation using a symmetric definite matrix:
$$
\mathcal{E}=\{(x,y): x=\textbf{C}u+d
$$
or:
$$
\begin{bmatrix}
x \\
y
\end{bmatrix}
=\begin{bmatrix}
c & d\\
d & f
\end{bmatrix}
\begin{bmatrix}
\cos(t) \\
\sin(t)
\end{bmatrix}
+\begin{bmatrix}
a \\
b
\end{bmatrix}
$$
I don't understand the following:

(1) According to the Python reference Python link to John-ellipsoid, in order for the ellipse to be inside the polygon or $\mathcal{E}\subset \mathcal{P}$, we must have $\textbf{A}(\textbf{C}u+d)\leq b$.

(2) According to the Matheamtica reference (under Geometry applications) ConicOptimication in Mathematica, to maximize the area is equivalent to minimizing $-\log(\text{Det}\textbf{C})$ which is equivalent to minimizing $-\text{Tr}(\textbf{C})$.

Would like to understand how (1) assures the ellipse is in the polygon and how (2) maximizes it's size and was hoping someone could help me.

Thanks!

[Moderator's note: Moved from a technical forum and thus no template.]

 

[Office_Shredder]

(1) seems pretty straightforward. Let x be a point in the ellipse. Then it's of the form Cu+d. If it's in the polygon, $Ax \leq b$. Plugging in Cu+d for x gives the result.

For part 2, do you know why the area of the ellipse is proportional to det(C)?

 

[aheight]

(1) seems pretty straightforward. Let x be a point in the ellipse. Then it's of the form Cu+d. If it's in the polygon, Ax≤b. Plugging in Cu+d for x gives the result.

For part 2, do you know why the area of the ellipse is proportional to det(C)?

Thanks, (1) is obvious now.

Regarding (2): I know the area of the ellipse is $A=\pi(ab)$ with a and b the major and minor axes. Also I know (2) has something to do with definite positive symmetric matrices and for square matrices, $\text{det}(\textbf{C})=\lambda_1\lambda_2$ which since positive definite, both eigenvalues will be positive so looks like $A=\pi ab=k\; \text{det}(\textbf{C})$. Is that correct?

And if I want to maximize $A=k\;\text{det}(\textbf{C})$ then that's equivalent to minimizing the ratio $\displaystyle\frac{1}{\text{det}(\textbf{C})}$.

Ok, since $\textbf{C}$ is a square matrix of a linear operator, we have $\text{tr}(\textbf{C})=\lambda_1+\lambda_2$ and it looks like, since the eigenvalues are both positive ( and $\log$ is monotonic), minimizing $\log(\text{det}\textbf{C})=\log(\lambda_1)+\log(\lambda_2)$ is equivalent to minimizing their sum or $\text{tr}(\textbf{C})$. Is that correct?

 

[Office_Shredder]

Every ellipse starts with a circle of radius 1, which just gives the identity matrix. The area of that is $\pi\det(C)$ by trivial math.

You then scale each axis by changing the value The area is proportional to the scaling, and the determinant is also proportional to the scaling. You then rotate it by applying a rotation matrix to C. The determinant and the area are both unchanged.

You then shift it by adding d, which also leaves both the area and determinant unchanged.

I agree with everything you said then up to the last step. Now that we are there, I'm confused why minimizing $\log(\lambda_1) + \log(\lambda_2)$ is the same as minimizing $\lambda_1+\lambda_2$.

Did they mean to say they are minimizing the trace of $log(C)$? I feel like there's probably something obvious here and someone else will make me look dumb by identifying it.

 

[aheight]

Now that we are there, I'm confused why minimizing $\log(\lambda_1) + \log(\lambda_2)$ is the same as minimizing $\lambda_1+\lambda_2$.

That was my proposition. Here's my proof:

Let $\lambda_1\lambda_2=u>0$ since both eigenvalues are positive. First note $\log(1/u)$ is monotonic decreasing for $u>0$ so we can write:
$$
\text{min}\left[-\log(\lambda_1\lambda_2)\right]=\text{min}\left[-(\log(\lambda_1)+\log(\lambda_2)\right]
$$
and since $\log(x)<x$ for $x>0$, then we may write:
$$
\text{min}\left[-(\log(\lambda_1)+\log(\lambda_2))\right]\lt \text{min}\left[-(\lambda_1+\lambda_2)\right]=\text{min}\left[-\text{tr}(\textbf{C})\right]
$$

Here's the Mathematica code used to find the inscribed ellipse of the polygon using this method:
[CODE title="Mathematica"]rp = RegionPlot[{
y - x <= 5/2 &&
y - 1/6 x <= 5/6 &&
y + 2 x <= 3 &&
-y - 1/10 x <= 4/5}, {x, -3, 2}, {y, -2, 2}, PlotRange -> 4]

polyA = {{-1, 1},
{-1/6, 1},
{2, 1},
{-1/10, -1}};

polyB = {5/2, 5/6, 3, 4/5};

constraints =
Table[Norm[polyA[].c] + polyA[].d <= polyB[], {i,
Length[polyA]}];
{cEllipse, dEllipse} = {c, d} /.
ConicOptimization[-Tr[c],
constraints, {c \[Element] Matrices[{2, 2}], d}]
aFine[d_, m_, t_] := d + m[[All, 1]] Cos[t] + m[[All, 2]] Sin[t];
ePlot = ParametricPlot[aFine[dEllipse, cEllipse, t], {t, 0, 2 Pi}];
Show[{rp, ePlot}, Axes -> True, PlotRange -> 4]
[/CODE]