Given minimal obstacles X, Y and Z, we rotated and reflected the disk as necessary so that segment XY is horizontal and located in the upper half-disk. Then:

- Obstacle Z can be located no higher than the lowest point of the small circle, otherwise there would exist a large feasible triangle in the part of the disk below Z.
- Z cannot be located below the long chord ending at L, otherwise we could draw a large feasible triangle by sliding L downward.
- Similarly, Z cannot be located below the long chord ending at M.

Altogether then, Z belongs to the (closed) grey triangular region, the bottom point of which is (0, −

*r*

_{0}).

An interesting thing about this situation is that the location, shape, and size of the grey triangle is independent of the precise location of points X and Y—these points aren't even shown on the diagram. One could translate segment XY arbitrarily within the upper part of the disk, or lengthen or shorten segment XY, and it would remain the case that Z would have to belong to the grey triangle—because the grey triangle was defined by considerations about the

*lower*half-disk. Of course, we almost certainly had to rotate and reflect the disk to make segment XY horizontal and up-top in the first place. So if you imagine

*not*doing that reflection and rotation step, then when you construct the grey triangle based on the location of X and Y, it will end up being rotated or reflected from what is shown above.

Here's an animation showing all of the possible locations of the shaded triangle. (I'm shading the triangle green from here on out. Also, note that the dashed circle has radius

*r*

_{0}.)

No matter how we orient the green triangle (i.e., no matter where X and Y are located), the green triangle can't escape the grey annulus, ½

*r*

_{0}≤

*r*≤

*q*, where

*q*= 0.36606…. Therefore, no matter where X and Y are located, obstacle Z belongs to the grey annulus.

But "Z" could be any of the three obstacles, so actually,

**All three obstacles in a minimal triple must belong to the annulus ½**

*r*_{0}≤*r*≤*q*.This is a pretty severe constraint, especially when combined with the result of from the previous post (any two obstacles in a minimal triple must be at least

*r*

_{0}Sqrt[3] apart).

***

Let's start again. Suppose {X, Y, Z} is a minimal set of obstacles, and rotate the disk if necessary so that segment XY is horizontal. Reflect if necessary so that segment XY is in the

*lower*half-disk. (The switch from upper to lower is just so that I can use my existing codebase for generating diagrams.) And finally, for definiteness, reflect once more if necessary so that X is to the left of Y. Then with reference to the figure below, Z belongs to the green triangular region, and horizontal segment XY belongs to the part of the grey annulus located below chord DE.

Segment XY has to be at least

*r*

_{0}Sqrt[3] long, which constrains its position in the annulus in several ways:

- The segment can't be too close to the bottom of the annulus, because the width of the annulus decreases as you move towards the bottom.
- The leftmost point can't be located very far to the right—there has to be a distance at least
*r*_{0}Sqrt[3] to the right-hand boundary of the annulus. - The rightmost point can't be located very far to the left—there has to be a distance at least
*r*_{0}Sqrt[3] to the left-hand boundary of the annulus.

Here's the real estate available for X and Y once we take into account these implications of the minimum separation requirement. Point X must belong to the blue region, and Point Y must belong to the red region.

Segment PQ represents an extreme case in the following sense:

(*) If a segment has one endpoint in the green triangle to the right of PQ, and passes tangent to the circle, then its other endpoint cannot be located in the blue region.

To see this, imagine choosing any point in the green triangle to the right of PQ, and from this point project a ray tangent to the circle: pretty clearly, this ray "flies too high" and misses the blue region entirely. This is because of the way the tangent to the circle "rocks" against the circle like a rocker-arm.

Thus, if a segment has one endpoint in the green region to the right of PQ, and another endpoint anywhere in the blue region, then the segment can't be tangent to the circle. Indeed such a segment enters the circle, i.e., it passes closer than ½

*r*

_{0}to the center of the disk.

This has implications for the location of point Z. If Z were located to the right of segment PQ, then segment ZX would necessarily pass closer than ½

*r*

_{0}to the center of the disk, and there would exist a large feasible edge-type triangle on the chord through ZX. (Feasible, because obstacle Y is safely away from this action.)

Conclusion: Z can't be located to the right of segment PQ. And by considering the red region analogously, Z can't be located to the left of segment RS either.

The allowable regions for X (blue), Y (red), and Z (green) are therefore as shown here:

***

Let's forget about the red and blue regions now. I was really only using them to help me clip off the annoying "wide lapels" of our initial green triangle. Having done that, we can now re-run the same annular arguments that we used for the initial green triangle.

Since the outermost point of the clipped green region is a distance

*r*

_{0}from the disk center, we can replace

*q*by

*r*

_{0}in the reasoning and conclude this time that

**All three obstacles in a minimal triple must belong to the annulus ½**

*r*_{0}≤*r*≤*r*_{0}.And with that, we're in the home stretch. In an annulus ½

*r*

_{0}≤

*r*≤

*r*

_{0}, the longest

*possible*segment that doesn't pass closer than ½

*r*

_{0}to the center is a segment of length

*r*

_{0}Sqrt[3] tangent to the inner circle.

This fact is probably standard, but at any rate I think it's not hard to see that the longest segment has to be a chord on the outer circle. (If either endpoint were in the interior, the segment could be lengthened; and if an endpoint were on the small circle, rotating the segment a bit about the other endpoint would free up some space to lengthen it again). And given that it's a chord, it's not hard to see that its length is maximized by pushing the chord toward the center until it's tangent to the inner circle.

What this means is that if all three pairs of obstacles must be at least

*r*

_{0}Sqrt[3] apart, then all three pairs of obstacles must be

*exactly*

*r*

_{0}Sqrt[3] apart, i.e., triangle XYZ is isosceles, with its sides tangent to the circle of radius ½

*r*

_{0}.

That is, {X, Y, Z} = {O

_{1}, O

_{2}, O

_{3}}.

***

Readers, please let me know if you see mistakes or lapses in the above! But assuming for now that it is basically right, we can add to our results in the Points In A Circle Problem.

GivenNobstacle points X_{1}, …, X_{N}in the closed unit disk, letdenote the greatest possible area of a triangle in the disk that doesn't strictly contain any of the Xa_{N}(X_{1}, …, X_{N})_{i}. LetThen for each given value ofa_{N}* = minimum possible value ofa_{N}(X_{1}, …, X_{N}).N, our problem is to calculatea_{N}* and find a minimal set of obstacles, that is,Npoints X_{i}* for whicha_{N}(X_{1}*, …, X_{N}*) =a_{N}*.

Known results so far:

*a*_{1}* = 1 and*a*_{1}(X) = 1 if and only if X = O, the center of the disk.*a*_{2}* = 1 and*a*_{2}(X_{1}, X_{2}) = 1 if X_{1}= O or X_{2}= O.*a*_{3}* = 0.8286369… and*a*_{3}(X_{1}, X_{2}, X_{3}) = 0.8286369… if and only if {X_{1}, X_{2}, X_{3}} = {O_{1}, O_{2}, O_{3}} in some orientation.

_{i}are equally spaced around a circle of radius

*r*

_{0}= 0.320963…. As noted in an earlier post, the value of

*r*

_{0}is given exactly by the real root of the cubic polynomial 5

*x*

^{3}− 4

*x*

^{2}+ 7

*x*− 2, namely

and the value of a

_{3}* is given exactly by positive root of the polynomial 160000

*x*

^{6}− 265824

*x*

^{4}+ 412857

*x*

^{2}− 209952, namely

***

Not all of the partial results from the past few months figured in the eventual solution to

*N*= 3. Mostly, the argument relies on the tension between edge triangles and spotlight triangles. Calculating a

_{3}(O1, O2, O3) to begin with was actually harder, I thought, than showing a

_{3}(X, Y, Z) ≥ a

_{3}(O1, O2, O3) for all X, Y, Z. Needless to say, there could be much easier ways of solving the problem than the ways I developed, and perhaps there are theorems known to experts that would make quick work of the problem.

Part of me is disappointed that a careful investigation of

*N*= 3 failed to turn up any better obstacles, or even any additional minimizers beyond the O

_{i}originally conjectured. But I guess I'm even more surprised that an initial, intuitive choice of obstacles eventually held up to scrutiny.

Speaking of scrutiny, I have listed our "known results"—but in mathematics, nothing is really known until it's proved to professional standards of rigor. I'm not under the illusion that this series of blog posts meets that standard. I've been approaching the Points In A Circle problem recreationally, not professionally. Some of the arguments I've made are solid, but many others are just sketches that would need filling in. Journal peer review would certainly reveal gaps, if not errors, along the way. Nevertheless, I don't have any plans right now to clean up the analysis or organize it more linearly.

Also, I plan to keep my promise and leave the

*N*= 4 problem to others!

## No comments:

Post a Comment