Sunday, March 5, 2017

Points In A Circle Problem: Solution for N = 3

Let's take another look at the second-to-last figure from the previous post.


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, −r0).

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 r0.)


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, ½r0 ≤ 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 ½r0rq.

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 r0Sqrt[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 r0Sqrt[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 r0Sqrt[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 r0Sqrt[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.


On the same figure, lay down Segment PQ as shown:


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 ½r0 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 ½r0 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 r0 from the disk center, we can replace q by r0 in the reasoning and conclude this time that

All three obstacles in a minimal triple must belong to the annulus ½r0 ≤ r ≤ r0.

And with that, we're in the home stretch. In an annulus ½r0 ≤ r ≤ r0, the longest possible segment that doesn't pass closer than ½r0 to the center is a segment of length r0Sqrt[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 r0Sqrt[3] apart, then all three pairs of obstacles must be exactly r0Sqrt[3] apart, i.e., triangle XYZ is isosceles, with its sides tangent to the circle of radius ½r0.

That is, {X, Y, Z} = {O1, O2, O3}.

***

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.

Given N obstacle points X1, …, XN in the closed unit disk, let
aN(X1, …, XN)
denote the greatest possible area of a triangle in the disk that doesn't strictly contain any of the Xi. Let
aN* = minimum possible value of aN(X1, …, XN).
Then for each given value of N, our problem is to calculate aN* and find a minimal set of obstacles, that is, N points Xi* for which aN(X1*, …, XN*) = aN*. 

Known results so far:
  • a1* = 1 and a1(X) = 1 if and only if X = O, the center of the disk.
  • a2* = 1 and a2(X1, X2) = 1 if X1 = O or X2 = O.
  • a3* = 0.8286369… and a3(X1, X2, X3) = 0.8286369… if and only if {X1, X2, X3} = {O1, O2, O3} in some orientation.
Here, the points Oi are equally spaced around a circle of radius r0 = 0.320963…. As noted in an earlier post, the value of r0 is given exactly by the real root of the cubic polynomial 5x3 − 4x2 + 7x − 2, namely


and the value of a3* is given exactly by positive root of the polynomial 160000x6 − 265824x4 +  412857x2 − 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 a3(O1, O2, O3) to begin with was actually harder, I thought, than showing a3(X, Y, Z) ≥ a3(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 Oi 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: