{"id":3612,"date":"2023-02-25T16:55:51","date_gmt":"2023-02-25T22:55:51","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3612"},"modified":"2023-02-26T09:24:10","modified_gmt":"2023-02-26T15:24:10","slug":"ellipse-packing","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/ellipse-packing\/","title":{"rendered":"Ellipse packing"},"content":{"rendered":"

You’ve heard of circle packing… Well this week’s Riddler Classic<\/a> is about ellipse packing!<\/p>\n

\nThis 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?<\/p>\n

Extra credit:<\/em> Instead of three smaller ellipses, what about other numbers of ellipses?\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\n

Solution approach<\/h3>\n

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.<\/p>\n

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.<\/p>\n

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
\n\\[
\nx^2 + 4y^2 \\leq 1
\n\\]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
\n\\[
\nE_i:\\quad\\frac{1}{2}\\begin{bmatrix}x-x_i\\\\y-y_i\\end{bmatrix}^\\top
\n\\begin{bmatrix}
\n5-3\\cos(2\\theta_i) & -3\\sin(2\\theta_i) \\\\
\n-3\\sin(2\\theta_i) & 5+3\\cos(2\\theta_i)
\n\\end{bmatrix}
\n\\begin{bmatrix}x-x_i\\\\y-y_i\\end{bmatrix}\\leq 1
\n\\]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:
\n\\[
\nE_r:\\quad r^2x^2 + 4r^2 y^2 \\leq 1
\n\\]<\/p>\n

The constraints we need to worry about are as follows:<\/p>\n