You’ve heard of circle packing… Well this week’s Riddler Classic is about ellipse packing!
This week, try packing three ellipses with a major axis of length 2 and a minor axis of length 1 into a larger ellipse with the same aspect ratio. What is the smallest such larger ellipse you can find? Specifically, how long is its major axis?
Extra credit: Instead of three smaller ellipses, what about other numbers of ellipses?
My solution:
[Show Solution]
Solution approach
This is a difficult problem, and I resorted to a rather brute-force computational approach. Roughly, I modeled the problem as a nonlinear (nonconvex) constrained continuous optimization problem, and then I threw a black-box optimizer at the problem with a large number of random initial guesses to help navigate the many local optima in the problem.
I parameterized each inner ellipse by the coordinates of its center $(x_i,y_i)$ and its orientation angle $\theta_i$. For the larger enclosing ellipse, I assumed it was centered at the origin with major axis length $r$. So for $n$ smaller ellipses, there was a total of $3n+1$ variables to solve for.
The interior of an ellipse with major axis length $2$ and minor axis length $1$ centered at the origin is the set of points $(x,y)$ that satisfy
\[
x^2 + 4y^2 \leq 1
\]If we rotate this ellipse by $\theta_i$ and translate the center to $(x_i,y_i)$, we get, after some algebra, the transformed equation
\[
E_i:\quad\frac{1}{2}\begin{bmatrix}x-x_i\\y-y_i\end{bmatrix}^\top
\begin{bmatrix}
5-3\cos(2\theta_i) & -3\sin(2\theta_i) \\
-3\sin(2\theta_i) & 5+3\cos(2\theta_i)
\end{bmatrix}
\begin{bmatrix}x-x_i\\y-y_i\end{bmatrix}\leq 1
\]We also have the outer ellipse, which we assumed has major axis length $r$ and is centered at the origin with no rotation. This has the equation:
\[
E_r:\quad r^2x^2 + 4r^2 y^2 \leq 1
\]
The constraints we need to worry about are as follows:
- The small ellipses do not intersect: $E_i \cap E_j = \emptyset$ for all $1 \leq i \lt j \leq n$.
- the small ellipses are inside the larger one: $E_i \subseteq E_r$ for all $1 \leq i \leq n$.
The optimization problem we’re solving is therefore:
\[
\begin{aligned}
\underset{x_i,y_i,\theta_i,r}{\text{minimize}} \qquad& r \\
\text{such that:} \qquad& E_i \cap E_j = \emptyset, \quad 1 \leq i \lt j \leq n \\
& E_i \subseteq E_r, \quad 1 \leq i \leq n
\end{aligned}
\]
There are various ways to specify the intersection and containment constraints, but I didn’t worry too much about it since I was going to use a black-box optimizer anyway. The method I chose was essentially to approximate the boundary of each ellipse as a polygon with a large number of vertices (I used 80). Then, containment or intersection between a pair of ellipses can be specified by enforcing that each point along the boundary of a given ellipse satisfy (or violate) the inequality defining the other ellipse. For each ellipse pair, I only used the point that yielded the worst constraint violation, thereby keeping the total number of constraints small.
For the actual implementation, I used MATLAB’s fmincon function, which uses an interior-point solver and approximates gradients using finite differencing. Roughly speaking, it repeatedly makes small adjustments to all the variables in an effort to reduce $r$ while satisfying all the constraints, and stops when it reaches a local optimum. It’s not pretty, but since the number of variables and constraints is relatively small, the algorithm is quite efficient (even in MATLAB!). As $n$ gets larger, the number of local minima also gets large, so it is increasingly likely that the solver will get “stuck” at a suboptimal solutions. To overcome this, I used 1000 random initializations for each $n$ and kept the best solutions.
Optimal packings
Here is what I found with $n=2,3,\dots,10$. I am fairly confident that I found the optimal configurations for the smaller $n$ I tried, but for the larger ones, it may be that 1000 random trials only scratches the surface and it is possible to find better packings that the ones I’m showing here. That being said, the best packings I found for even $n$ were configurations that have 180-degree rotational symmetry. When $n$ is odd, however, the packings are much more difficult to reason about. (click to see the full-sized image)
To show the effect of changing the initialization for the optimizer, here are the top 12 best solutions found by the optimizer for the case $n=10$. As we can see, there are many different configurations that yield a similar quality of solution. This is why the problem becomes increasingly difficult as we increase $n$; there are many “good” configurations, so it is difficult to find the best one.
Symmetric (suboptimal) packing
Another way to get a solution for the case $n=3$ is to consider the optimal packing of three circles inside another circle. There are infinitely many such arrangements, since we have rotational symmetry.
Then, if we stretch each such configuration horizontally by a factor of $2$, we obtain a valid packing of three ellipses, and again there is an infinite family with a kind of rotational symmetry. If each of the smaller ellipses has a width of $2$, then the larger ellipse has a width of $\frac{4}{\sqrt{3}}+2 \approx 4.3094$. This is not as good as the packing we found above using optimization, which yielded $3.8759$. The reason for the difference is that the symmetric solution assumes the major axes of all four ellipses are aligned. It turns out that if you don’t align the ellipses, you can do better!