Saturday, November 12, 2016

Points In A Circle Problem: Note on N = 3

Our problem is
Place N points in the unit disk in such a way as to minimize the greatest possible area of a triangle in the disk that doesn't contain any of the points.
See the solution for N = 1, the solution for N = 2, and the conjecture for N = 3.

In this post, I'll reduce the possibilities somewhat for the N = 3 case, making no assumptions about the locations of the obstacle points. At the end, I'll apply what we learn to the particular obstacles in the conjectured optimum configuration.

Reducing the possibilities

Given three distinct obstacle points located anywhere inside the unit disk, I think it isn't hard to show that a greatest-area feasible triangle must satisfy one among the following three conditions:

(i) All three vertices of the triangle are on the boundary of the disk.

(ii) Exactly two vertices are on the boundary of the disk, and both sides meeting the interior vertex have one or moretwo obstacle points on them.

(iii) No vertices are on the boundary of the disk, and Each proper side has one obstacle point on it.

(A triangle's "proper sides" are what remains after you delete the three vertices. This is a term I made up.)

I established that one of the conditions (i)–(iii) must hold by considering the following ten cases:
  • 3 obstacles on vertices of the triangle, 0 obstacles on proper sides, 0 obstacles outside the triangle
  • 2 obstacles on vertices of the triangle, 1 obstacles on proper sides, 0 obstacles outside the triangle
  • 2 obstacles on vertices of the triangle, 0 obstacles on proper sides, 1 obstacles outside the triangle
  • 1 obstacles on vertices of the triangle, 2 obstacles on proper sides, 0 obstacles outside the triangle
  • 1 obstacles on vertices of the triangle, 1 obstacles on proper sides, 1 obstacles outside the triangle
  • 1 obstacles on vertices of the triangle, 0 obstacles on proper sides, 2 obstacles outside the triangle
  • 0 obstacles on vertices of the triangle, 3 obstacles on proper sides, 0 obstacles outside the triangle
  • 0 obstacles on vertices of the triangle, 2 obstacles on proper sides, 1 obstacles outside the triangle
  • 0 obstacles on vertices of the triangle, 1 obstacles on proper sides, 2 obstacles outside the triangle
  • 0 obstacles on vertices of the triangle, 0 obstacles on proper sides, 3 obstacles outside the triangle
(That there are ten cases checks out, since we are effectively putting three indistinguishable balls into three distinguishable boxes, and there are 3 + 3 − 1C3 − 1 = 5C2 = 10 ways to do that.)

(It isn't clear that you have to go to the trouble of distinguishing between obstacles at vertices and obstacles on proper sides—everything seems to work out continuously in practice—but I didn't want to assume so.)

Some of these cases have two or more sub-cases. For example, here are the sub-cases when all three obstacle points lie on proper sides of the triangle. There are sub-cases because the greatest number of points on a single proper side could be three, two, or one. (The obstacle points are colored blue; the reason for the orange vertices is explained shortly.)


In the upper-left configuration, maximality implies that none of the three vertices are in the interior of the disk, because if any vertex were in the interior, that vertex could be perturbed in such a way as to increase area while maintaining feasibility. But in the other three configurations, there are triangle vertices (colored orange) that can't be perturbed, at least not in the same way. A simple perturbation strategy can't drive the orange vertices to the disk boundary.

The possibilities (i), (ii), (iii) listed earlier jointly summarize the state of affairs after all of the ten cases and their associated subcases have been examined, with the easy-to-perturb configurations ruled out.

In the rest of this post, I'll analyze possibility (ii): "Exactly two vertices are on the boundary of the disk, and both sides meeting the interior vertex have one or more obstacle points on them." We'll label the interior vertex C.

Given the three obstacle points, some two of them are together on one of the proper sides of the triangle. (Generically there are three choices for this pair.) The line through those two obstacle points thus passes through vertex C, and the line through those two obstacle points meets the boundary of the disk in another vertex of the triangle, label it B. The line through C and the remaining obstacle point meets the boundary of the disk in the final vertex of the triangle, label it A. For a specific configuration of obstacle points, and for a specific choice of the pair of obstacles to be with one another on a side, the situation looks like this:


There was one degree of freedom in drawing this figure: it could be described as the freedom to choose the distance between vertex C and the obstacle on CB that is closer to C. That is, once you've decided which two obstacle points will be together on a side, you get to decide how far C will be from B.

Sliding C along its degree of freedom makes side CA "swing" on the pivot of the third obstacle point, thus changing the area as shown in this video:

video

In scenario (ii), then, given the obstacle points, and given a choice of which two obstacle points to pair on a side of the triangle, the area of the triangle can be determined as a function of a single variable. If the function is found explicitly, it can be analyzed to find the maximum area. The maximizer so discovered can be pitted against the maximizers that result from the other two choices for the paired obstacles, and the overall winner becomes the maximizer for scenario (ii).

Observe from the video that the best triangle for this family of possibilities occurs when vertex C has moved about halfway to the disk boundary, resulting in an area of about 0.803. It seems the winning triangle from scenario (ii) could indeed have a vertex in the interior of the disk, depending on the arrangement of the obstacle points.


Applying this to the particular configuration of obstacles conjectured to be optimal

I'll end with some concrete progress on the N = 3 problem. I carried out the above analysis for the particular case of the conjectured optimum triple of obstacle points, and because the geometry in that case is tractable, I could produce the explicit function giving the triangle area as a function of the variable distance parameter. Here's a relevant page from my notebook (the notation doesn't match the above, this is just for fun).


The area function is long and complicated to write down, but it's a smooth function, and so I just graphed the thing. The graph of the area as a function of the variable distance is the blue curve here:


(There are also some black curves, because I wanted to show the smoothness of the result as we allow the configuration of obstacles to "breathe" a little bit by moving in unison towards or away from the center of the disk.)

The blue curve is monotonically increasing (more obvious to the eye when you graph the derivative, which never gets close to zero). Hence the greatest area is obtained by allowing point C to move all the way out to the boundary, resulting in the spotlight triangle from this post.

Thus, scenario (ii) has no triangles that exceed the spotlight triangle and the edge triangle in area, and we can proceed to analyze scenarios (i) and (iii). This moves us closer to showing that for the conjectured triple of obstacles, the greatest possible area is the area 0.828... attained by spotlight triangle and edge triangle. By the way, if the greatest possible area really is less than 1, it rules out any possibility of recycling the argument for N = 2 in the N = 3 case.


P.S.

For the three obstacle points shown in the video, the greatest possible scenario-(ii) area was 0.803. That's less than the greatest possible area for the conjectured optimum configuration of obstacles (0.828...). However, the obstacle points shown in the video don't unseat the conjectured optimum configuration of obstacles, because for the obstacle points shown in the video, there is a scenario-(i) triangle with area 1.037. (I found it using a numerical solver I made a while back.)


No comments: