Imagine you’re rolling down the street in a driverless car when you see a problem ahead. An Amazon delivery driver got their van halfway past a double-parked UPS truck before realizing they couldn’t make it through. Now they’re stuck. And so are you.
The street is too narrow to pull off a U-ey, so your AI-enhanced automobile initiates a three-point turn. First, the car takes a curving path toward one curb. Once there, it steers the other way and backs up to the opposite curb. Then it turns the steering wheel back in the direction of the first curving path, driving forward and away from the obstruction.
This simple geometric algorithm of making intermediate turns can help you get around in tight situations. (If you’ve ever parallel parked, you know what this back-and-forth wiggling can do for you.)
There’s a fun math problem here about how much space you need to turn your car around, and mathematicians have been working on an idealized version of it for over 100 years. It started in 1917 when the Japanese mathematician Sōichi Kakeya posed a problem that sounds a little like our traffic jam. Suppose you’ve got an infinitely thin needle of length 1. What’s the area of the smallest region in which you can turn the needle 180 degrees and return it to its original position? This is known as Kakeya’s needle problem, and mathematicians are still studying variations of it. Let’s take a look at the simple geometry that makes Kakeya’s needle problem so interesting and surprising.
Like many math problems, this one involves some simplifying assumptions that make it less realistic but more manageable. For instance, the length and width of a car matter when you’re driving, but we’ll assume that our needle has length 1 and width zero. (This means the needle itself has an area of zero, which plays an important role in allowing us to solve the problem.) Also, we’ll assume that the needle, unlike a car, can pivot around its front end, its back end, or any point in between.
The goal is to find the smallest region that allows the needle to turn 180 degrees. Finding the smallest thing that satisfies a certain set of conditions can be challenging, but a good way to start is to look for anything that satisfies those conditions and see what you can learn along the way. For example, an easy answer is to just rotate the needle 180 degrees around its end point, and then slide it back up. This returns the needle to its original position, but it’s now pointing in the opposite direction, as Kakeya’s needle problem requires.
The region required for the turn is a semicircle with radius 1, which has an area of $latex A=frac{1}{2} pi r^2=frac{1}{2} pi (1)^2=frac{1}{2} pi=frac{pi}{2}$. So we’ve found one region that works.
We can do better by taking advantage of our magical mathematical needle’s ability to rotate about any point. Instead of rotating it about its endpoint, let’s rotate it about its midpoint.
You might call this Kakeya’s compass: Our needle starts out pointing north, but after rotation it’s in the same spot but pointing south. This region is a circle of radius $latex frac{1}{2}$, so its area is $latex A=pi r^2=pi (frac{1}{2})^2=pi frac{1}{4} =frac{pi}{4}$. This is half the area of our first region, so we’re making progress.
Where to next? We could take inspiration from our driverless-car dilemma and consider using something like a three-point turn for the needle. This actually works pretty well.
The region swept out by the needle using this technique is called a deltoid, and it too satisfies Kakeya’s requirements. Computing its area requires more than the elementary geometry we’re discussing here (knowledge of parametric curves helps), but it turns out that the area of this particular deltoid — the one swept out by a line segment of length 1 — is exactly $latex frac{pi}{8}$. Now we have an even smaller region in which we can turn Kakeya’s needle around, and you could be forgiven for thinking this is the best we can do. Kakeya himself thought it might be.
But this needle problem took a big turn when the Russian mathematician Abram Besicovitch discovered you can do infinitely better. He came up with a procedure to whittle away unnecessary bits of the region until it was as small as he wanted.
The process is technical and complicated, but one strategy based on Besicovitch’s idea relies on two simple ideas. First, consider the right triangle below, with a height of 1 and a base of 2.
For the moment we’re going to forget about turning the needle completely around and just focus on one simple fact: If we place a needle of length 1 at the top vertex, the triangle is big enough to allow the needle to rotate the full 90 degrees from one side to the other.
Since the area of the triangle is $latex A=frac{1}{2}bh$, this triangle has area $latex A=frac{1}{2} times 2 times 1=1$.
Now, here’s the first important idea: We can reduce the area of the region while preserving the 90-degree rotation. The strategy is simple: We cut the triangle down the middle, and then push the two halves together.
The area of this new figure must be less than the original because parts of the triangle now overlap. In fact, it’s easy to compute the area of the figure: It’s just three-fourths of the square of side 1, so the area is $latex A=frac{3}{4}$, which is less than the area of the triangle we started with.
And we can still point the needle in all the same directions as before. There’s just one problem: The original angle has been split into two pieces, so those directions are now divided into two separate regions.
If the needle is on the left side of the new region, we can rotate it the 45 degrees between south and southeast, and if it’s on the right we can rotate it the 45 degrees between south and southwest, but since the two parts are separated, it doesn’t seem as if we can rotate it the full 90 degrees as we could before.
This is where the second important idea comes in. There’s a sneaky way to get the needle from one side to the other that doesn’t require much area. In chess you may know that the knight moves in an L shape. Well, our needle is going to move in an N shape.
Here’s how it’s done. First, the needle slides up one side of the N. Then it rotates to point along the diagonal and slides down. Then it rotates again and finishes its trip by sliding up the other side of the N.
At first this N-shaped move may not look like much, but it does something very useful. It allows the needle to “jump” from one parallel line to another, which will help us get our needle from one region to the other. More importantly, it does so without requiring much area. In fact, you can make it require as little area as you like. Here’s why.
Recall that our needle has zero width. So any line the needle moves along, forward or backward, will have zero area. This means the region required to move the needle up, down or diagonally along the N shape will be made up of pieces with zero area.
That just leaves the rotations at the corners of the N shape.
These moves do require area. You can see a little sector of a circle at each corner. But here’s the sneaky part: You can make these regions smaller by elongating the N.
The formula for the area of a sector of a circle is $latex A=frac{theta}{360} pi r^2$, where $latex theta$ is the measure of the sector’s angle in degrees. No matter how tall the N is, the radius of the sector will always be 1: That’s the length of the needle. But as the N gets taller, the angle shrinks, which will reduce the area of the sector. Thus, you can make the additional area as small as you want by stretching out the N as much as you need.
Remember that we were able to reduce the area of our triangular region by splitting it in two and making the pieces overlap. The problem was that this split the 90-degree angle into two separate pieces, preventing us from rotating the needle the full 90 degrees. Now we can solve that problem by tacking on an appropriate N shape to ensure that the needle has a path from one side to the other.
In this updated region, the needle can still rotate the full 90 degrees as before, it just now happens in two stages. First, the needle turns 45 degrees and lines up with the vertical edge on the left. Next, it moves along the N shape to get to the other side. Once it’s there, it’s free to turn the other 45 degrees.
This moves the needle 90 degrees, and to keep it turning, you just add rotated copies of the region.
With the addition of the appropriate N shapes, the needle can jump from one triangular peninsula to the next, turning itself bit by bit until it gets all the way around, just like a car executing a three-point turn.
There’s more devilish math in the details, but these two ideas — that we can continually reduce the area of the original region by slicing it up and shifting it around while ensuring we can get from piece to piece using the arbitrarily small N shapes — help us move the needle in an ever-shrinking region that can ultimately be as small as you want.
A more standard approach to building this kind of region begins with equilateral triangles and uses “Perron trees,” which are clever ways to slice triangles up and stretch and slide the pieces back together. The result is quite stunning.
Recently, mathematicians have made progress on new variations of this old problem, set in higher dimensions and with different notions of size. We’ll probably never see an AI-powered car tracing out a Kakeya-needle-point turn, but we can still appreciate the beauty and simplicity of its near nothingness.
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/how-simple-math-moves-the-needle-20230929/
