Sunday, January 15, 2017

Points In A Circle Problem: Various Notes On N = 3

I haven't had much time to think about the problem lately, what with all the Holiday Challenge action, but there are a few notes from my notebook that I thought I would record. I'll begin by stating the problem once again using our compact notation.

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*. 

So far, here is what we know:
  • 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* ≤ a3(O1, O2, O3) = 0.8286369…, a value we'll abbreviate by A0.
Here, the points Oi are equally spaced around a circle of radius r0 = 0.320963….

Now the notes (edited 1/16/2017 to correct the error noted below in the comments):

1) If all three obstacle points are located a distance at least 0.798677… from the disk center, then an equilateral triangle inscribed in a centered circle of radius 0.798677… is feasible and has area greater than A0. Such a set of obstacle points therefore can't be minimal. (We'll strengthen this statement at the end of the post.)

2)  Because the long side of an edge triangle passes the disk center at a distance ½r0 = 0.16048… from the origin, it follows that if any obstacle point were located less than a distance 0.16048… from the origin, then we could produce a feasible triangle of area greater than by A0 by first drawing a feasible edge triangle and then pushing its long side inward toward the center. (To see that a feasible edge triangle exists, first rotate and reflect the disk if necessary so that any obstacles with r ≥ 0.16048… are in the closed upper half-disk. Then the edge triangle to the bottom of the disk is feasible.) Thus, a set of minimal obstacles must be confined to the annulus 0.16048 ≤ r < 1.

Confining the minimal obstacles to an annulus or some other two-dimensional region probably doesn't help fundamentally with solving the problem, because it doesn't reduce the problem's dimensionality. However, confining the obstacles could conceivably help with ruling out various cases one might find oneself considering; and it does reduce the acreage of the problem, which could increase the power of some numerical experiments.

Continuing with items from the notebook:

3) A natural question to ask is whether the conjectured minimal set {O1, O2, O3} is stable. That is, could you perturb the Oi slightly and obtain a better set of obstacles?

I think not…when I wrote a quickie computer program to evaluate several million small perturbations of the triple, for every perturbation the computer was able to find a triangle of area greater than A0 (by checking the perturbed edge and spotlight triangles). This isn't a proof of stability, of course. (Nor would a stability proof be enough by itself to establish that the Oi are a minimal set: better obstacles might exist but not be obtainable by a small perturbation of the Oi.)

One easy result that at least relates to stability is the following: If {X, Y, Z} is a minimal set of obstacles and triangle XYZ is congruent to triangle O1O2O3 by a rigid motion with a sufficiently small translation, then {X, Y, Z} is a rotation of {O1, O2, O3}. In simpler terms: if you hold triangle O1O2O3 rigid and nudge it off the center of the disk, possibly with some rotation, then the resulting points are no longer a minimal set of obstacles.

To see this, let t be the nonero vector pointing from the center of the disk to the center of triangle XYZ. Translate triangle XYZ back to the center of the disk via −t to form triangle X'Y'Z'. Triangle X'Y'Z' is just a rotation of triangle O1O2O3, which means that the edge triangles through the sides of triangle X'Y'Z' all have area A0. Now define the unit vector u1 pointing directly away from Y'Z', unit vector u2 pointing directly away from Y'X', and unit vector u3 pointing directly away from X'Z'. Now, you can't run against all three of these directions at once: at least one of the inner products t·ui must be positive. This is easy to show by a sketch, or by choosing coordinates so that u1 = (0, 1), u2 = (Sqrt[3]/2, −½), u3 = (−Sqrt[3]/2, −½), and t = (tx, ty). So if, say, t·u1 is positive, then for sufficiently small ||t||, the area of the edge triangle through YZ exceeds the area of the edge triangle through Y'Z'. But the edge triangle through Y'Z' has area A0, so the area of the edge triangle through YZ exceeds A0, and the obstacles X, Y, Z are not a minimal set.

4) Because the problem of N + 1 obstacles includes the problem of N obstacles as a special case, we have aN* ≤ aM* whenever NM.

Proof (example): Suppose {P, Q, R, S} is a minimal set of obstacles for N = 4, and {X, Y, Z} is a minimal set obstacles for N = 3. Then we have

a4(P, Q, R, S) = a4* ≤ a4(X, Y, Z, Z) = a3(X, Y, Z) = a3*

so that a4* ≤ a3*.

Because of this, any bound we find for small N becomes a bound on all higher values of N also. (The N = 3 bound a3* ≤ A0 implies the bound aN* ≤ A0 for all N ≥ 3.)

5) A minimal set of 3 or more obstacles can't consist of collinear points. If the obstacles were collinear, there would exist a feasible triangle of area 1, which exceeds A0, so that the obstacles couldn't be minimal.

6) For any diameter of the disk, there must be at least one obstacle on either side of that diameter, otherwise again there would exist a feasible triangle of area 1. (From this it also follows that any diameter of the disk contains at most one obstacle.)

7) Let's draw the three edge triangles ABC, DEF, GHI passing through points O1, O2, and O3:


If all three obstacle points X, Y, Z were to be located outside of any single edge triangle, then that edge triangle could be perturbed to create a feasible triangle of greater area. So the apportionment of minimal obstacle points among the 22 regions shown is not arbitrary. For example, it is easy to check that every region in the diagram falls outside of some edge triangle, so that in a minimal set of obstacles, no single open region can contain all three obstacle points.

8) Let's go further and draw not only the three edge triangles ABC, DEF, GHI, but also the six spotlight triangles ABJ, ABK, DEL, DEM, GHN, GHP:


In this diagram, the regions are sub-regions of the regions in the previous diagram. Therefore all three obstacles in a minimal set can't be located in any single region of this diagram either. And similarly to before, if all three obstacles in a minimal set were to be located outside of any one of the nine triangles, then that triangle could be perturbed to create a feasible triangle of greater area. So again the apportionment of minimal obstacle points among the regions is not arbitrary.

There are 82 regions altogether, which results in 95,202 ways to place the obstacle points. Listing these ways with a computer is easy; in Mathematica we can do it like this:

Flatten[Map[Permutations, IntegerPartitions[3, {82}, {0, 1, 2}]],1]

It is also easy to tell the computer which regions belong to which triangles, enabling an automated check of whether any given apportionment of the three points results in a forbidden circumstance of all three obstacle points lying outside of any of the nine triangles that define the figure. The configurations falling afoul of this rule then get culled.

For example, one of the configurations that gets culled is this one, because putting an obstacle point in each of the shaded regions leaves all of the obstacle points outside of triangle ABJ. You could slide vertex J downward and it would increase the altitude on side AB, thus increasing the area beyond A0; this shows that the implied set of obstacles is not minimal.


One of the configurations that survives the culling is this one:



You can verify that placing an obstacle point in each of the shaded regions guarantees that all nine of the triangles contain at least one obstacle point. The bottom region guarantees triangles ABJ, ABK, DEF, GHN, and GHP; the region touching that one guarantees triangles ABC, DEL, DEM; and the region near the top guarantees triangle GHI.

A total of 411 configurations survive, and by telling the computer which regions map to which regions under symmetries of the figure, these can be reduced to 79 distinct configurations. Here is an animation showing all 79 of them:


Certain regions of the diagram are absent from all of the valid configurations; therefore in a minimal set of obstacles, no obstacle point can be located in these regions. The forbidden regions are shaded here:


Of course, we could have drawn the original nine triangles oriented at some other angle. If a region is excluded in one orientation, it is excluded in all orientations. This means that no obstacle point in a minimal set can be so far from the origin that it belongs to some forbidden region in any orientation. The innermost point of any forbidden region is located a distance 0.76664… from the center of the disk. This shrinks the annulus to which obstacle points in a minimal set must belong: the known bounds are now r ≥ 0.16048… and r ≤ 0.76664….

3 comments:

Bill McCallum said...

In (1) and (2) what you really wanted was "if one of the obstacle points is located . . . " rather than "if all obstacle points are located . . . " in order to be able to conclude that all points must be confined to the annulus. This is fine for (1), because if one of the points is less than 0.16408 ... from the center then you can find edge triangle that avoids the other two no matter where they are. But it does work for (2) as far as I can see. However, that doesn't matter since by the end of the post you have found a better bound anyway. Very nice argument there.

Jason Zimba said...

Thanks! I will correct it as soon as I can.

Jason Zimba said...

I think the logic is correct now. I also fixed the numerical value 0.14... and interchanged some less-thans and less-than-equals.