In 1917, Kakeya proposed a simple problem:

    \indent{\em What is the smallest area required to rotate a needle (line segment of length 1) by $180^\circ$ in the plane?}

This exact statement was solved in 1927, but refinements of this statement are still being researched. One refinement, the so-called Kakeya conjecture, was solved by a former UCLA professor just this year! In this section, we'll explore Kakeya's original statement.

In our area, we can {\em rotate} or {\em translate} the needle. We are not allowed to pick it up. Below is a (very inefficient) area showing how we might move our needle.
\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\linewidth]{img/silly-needle.jpg}
    \caption{A very inefficient region for the Kakeya needle problem.}
\end{figure}

\begin{problem}{}
    Try to construct a region within which you can rotate the needle $180^\circ$. Can you think of any such regions? What are their areas?\\
    {\em Hint: there's no need to be fancy here. We're just looking for a starting point.}\\
    (Open-ended) What's the smallest region you can find?
\end{problem}
\pagebreak

\begin{problem}{{\em Rough} upper bound} <rough rough bound>
    Starting with the needle straight up, rotate the needle $180^\circ$ about one of its ends. \\
    What region is swept out by this rotation? What is the area of this region?
\end{problem}
\begin{solution}
    This sweeps out a semicircle with area $\pi/2$.
\end{solution}
\vfill

\begin{problem}{Rough upper bound}
    What happens if you fix a different point of the needle and rotate about that point? What region is swept out by this rotation? What is the area of this region?\\
    {\em Choose a point distance $x$ from the end of the needle and rotate the needle $180^\circ$ about this point.}

    Using this method, what is the minimum area required? Which rotation point gives this area?
\end{problem}
\begin{figure}[h]
    \centering
    \includegraphics[width=0.65\linewidth]{img/needle_rotate.jpg}
\end{figure}
\begin{solution}
    This sweeps out two semicircles, one with radius $x$ and one with radius $(1-x)$. The total area is $\frac{\pi}{2}(x^2 + (1-x)^2)$ and is minimized when $x = 1-x = 1/2$ (rotating about the midpoint). This corresponds to an area of $\pi/4$.
\end{solution}
\pagebreak

\begin{problem}{Better upper bound} <better bound>
    Instead of picking one point to rotate about, suppose we change the point midway.

    Choose one end of the needle. Rotate the needle $60^\circ$ around this end. Then, rotate another $60^\circ$ about the other end of the needle. Repeat this process, alternating which end we rotate about, until the needle has rotated a full $180^\circ$. What area was swept out?

    Repeat this process, but instead rotating $90^\circ$ each time. Did the area increase or decrease?\\

    What happens if we try a smaller angle like $45^\circ$ or $30^\circ$? {\em No need to find exact numbers for this. Just get a sense of whether the area is increasing or decreasing.}
\end{problem}
\begin{solution}
    Rotating $60^\circ$, we sweep out a triangle with rounded sides (same as in curves of constant width). This has area
    \begin{equation*}
        A = 3*\tfrac{\pi}{6} - 2*\tfrac{\sqrt{3}}{4} = \tfrac{\pi}{2} - \tfrac{\sqrt{3}}{2} \approx 0.705 
    \end{equation*}
    The $\pi/6$ corresponds to the area of a $60^\circ$ slice of a unit circle, of which we have $3$. But then the equilateral triangle in the middle is triple-counted, so we subtract off twice the area.

    Rotating $90^\circ$ twice, we find the intersection of two quarter-circles. We break this down into two circular arcs of $30^\circ$ and one equilateral triangle with side length $1$. This gives an area of
    \begin{equation*}
        \tfrac{\pi}{6} + \tfrac{\sqrt{3}}{4} \approx 0.957.
    \end{equation*}

    With smaller angles, we find that our shape is getting closer to a circle of diameter $1$, like the previous problem and so it is getting bigger.
\end{solution}
\pagebreak


The key to this problem is to re-use space. In \ref{rough rough bound}, the needle passed through each point of our region only once. However, in \ref{better bound} the needle rotates through {\em most} points 3 times. Let's try to do better by introducing some translations.
\begin{problem}{Best convex bound}
    Start with the needle straight up and rotate clockwise by $60^\circ$ around the bottom of the needle. Instead of rotating again, shift the needle in the direction it is pointing by some fixed amount. \\
    {\em (We'll find the optimal amount soon. For now, shift by a large amount, say $2$. See the figure.)} \\
    Now rotate another $60^\circ$ around the top of the needle before shifting again. Continue this process until the needle rotates a full $180^\circ$.

    When we shift the needle a large amount, what shape is made? If we make this shift smaller, what happens to the region that we sweep out?

    By choosing the proper shift, we can make the region an equilateral triangle. What is the area of this triangle?
    How does this compare to our earlier regions?
    
    
\end{problem}
\begin{figure}[h]
    \centering
    \includegraphics[width=0.50\linewidth]{img/better-kakeya.jpg}
\end{figure}
\begin{solution}
    The equilateral triangle will have height $1$, with side length $2/\sqrt{3}$. This gives an area of $1/\sqrt{3} \approx 0.577$ and a shift of $2/\sqrt{3} - 1$.
\end{solution}
\vfill
{\em As it turns out, this triangle is the best you can do with a convex region!}
\pagebreak

\problem{(Bonus, challenge)}
    In 1927, Besicovitch solved the Kakeya needle problem by showing that you can construct a region with arbitrarily small area! The construction of this is fairly complicated, but relies on the idea we developed earlier: re-using as much space as possible.
    We won't detail the full construction here; this is just the general idea. Feel free to ask your instructor for more details!

    Let $T_1, T_2$ be adjacent triangles with bases of length $b$ on a line $L$ and heights $h$, as shown in the figure. If we slide $T_2$ a distance $2(1-\alpha)b$ to the left, we can overlap the triangles a small amount. 
    \\ What is the total area of $T_1$ and $T_2$ originally?
    \\ What is the difference in area between these two regions? (The area of the intersection.)
    \\ What $\alpha$ minimizes the area of our final region? How does the area of $S$ compare to $T_1$ and $T_2$?
\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\linewidth]{img/besicovitch_1.png}
\end{figure}
\begin{solution}
    Originally, $T_1 \cup T_2$ has area $bh$.
    
    The overlapping region is a pentagon with base $2(1-\alpha)b$. We can split this into two trapezoids with 'height' $(1-\alpha)b$, long base $h - h(1-\alpha)$, and short base $h - 2h(1-\alpha)$. This gives the overlapping region an area of
    \begin{equation*}
        (1-\alpha)b(2h - 3h(1-\alpha)) = bh(1-\alpha)(3\alpha - 1)
    \end{equation*}
    the difference in area is then given by
    \begin{equation*}
        |T_1 \cup T_2| - |S| = (1-\alpha)b(2h - 3h(1-\alpha)) = bh(1-\alpha)(3\alpha - 1).
    \end{equation*}
    To maximize this difference, we want $1-\alpha = 3\alpha - 1$ and hence $\alpha = 1/2$. Therefore $|S| = 3|T_1 \cup T_2|/4$. Wow!
\end{solution}
\pagebreak

\problem{(Bonus, challenge) continued}
If we begin with an equilateral triangle of height $1$, note that we can rotate a needle $60^\circ$ within the triangle. By doing this overlapping procedure, we can still rotate the needle $60^\circ$, now we have to do it in two 'steps'. We can rotate $30^\circ$ within $T_1$ and $30^\circ$ within $T_2$ and we've reduced the area we need!

However, in order to rotate the full $60^\circ$, we need to be able to move our needle between $T_1$ and $T_2$ without using two much extra area. How can you move the needle from $T_1$ to $T_2$ using an arbitrarily small area? Draw the resulting region.\\
{\em Hint: use the Kakeya squeegee problem from the warm-up.}
\begin{solution}
    This will look exactly like the previous figure, just with the Kakeya squeegee solution connecting the top of $T_1$ with the top of $T_2$.
\end{solution}

\vfill

To get our area even lower (arbitrarily low, in fact), we need to decompose our triangle even further. See the following figure for how we do that.
With the Kakeya squeegee problem, this allows us to rotate our needle $60^\circ$ in an arbitrarily small area. All we need to do then is connect three of these so-called {\em Perron trees} and we have solved the Kakeya problem.
\begin{figure}[h]
    \centering
    \includegraphics[width=0.75\linewidth]{img/besicovitch_2.png}
\end{figure}


\pagebreak