Saturday, October 22, 2016

Points In A Circle Problem: Solution for N = 2

The problem we've been considering 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.
Note that the sense of 'containing a point' is strict: if a point lies on the boundary of a triangle, the triangle is not considered to contain the point.

Click here for my conjectured solution for N = 3 and an overview of my solution for N = 1.

The result for N = 1 is just what you'd expect: placing the obstacle point in the center of the disk minimizes the greatest possible area of a triangle in the disk that doesn't contain the point. The center of the disk is the unique point that minimizes the greatest area.

The N = 2 problem is
Place two points in the unit disk in such a way as to minimize the greatest possible area of a triangle in the unit disk that doesn't contain either point.
Unless I'm mistaken, the solution to N = 2 follows easily from the solution for N = 1, as follows.

To economize on words, let's introduce a bit of notation. Given two obstacle points X and Y in the closed unit disk,

  • let a(X, Y) denote the greatest possible area of a triangle in the disk that doesn't contain X or Y.
  • let a* be the minimum possible value of a(X, Y).

Our problem is to calculate a* and find a pair of points X* and Y* for which a(X*, Y*) = a*.

(I take the indicated extreme values to exist; this seems safe given the closed and bounded features of the problem.)

Now to begin with, if O is the center of the disk, then from the N = 1 case we know that a(O, O) = 1. Therefore a* cannot be greater than 1.

Furthermore, a* cannot be less than 1, because there are no obstacles X and Y for which a(X, Y) is less than 1. This we show as follows:

1. If X and Y are coincident, then from the N = 1 case, we know that a(X, X) is at least 1.

2. Next suppose X and Y are distinct. Now, either X and Y are collinear with the center of the disk, or else X and Y are not collinear with the center of the disk.

2(a). If X and Y are collinear with the center of the disk, then some diameter of the disk passes through both X and Y. Thus, either of the two 45-45-90 triangles with that diameter as the hypotenuse are feasible. This shows again that a(X, Y) is at least 1.

2(b). If X and Y are not collinear with the center of the disk, draw diameter AB parallel to XY. Both X and Y are on the same side of AB. Therefore, one of the two 45-45-90 triangles with hypotenuse AB will be feasible, so that again a(X, Y) is at least 1.

Thus, for all possible obstacle points X and Y, a(X, Y) is at least 1. Hence, a* cannot be less than 1.

Since a* cannot be greater than 1, and a* cannot be less than 1, it follows that a* = 1. Therefore 1 is the smallest possible area of a greatest area triangle in the disk not containing two obstacle points.

To attain this minimum, one may place the first obstacle point at the center of the disk and the second obstacle point anywhere in the disk.

(Because triangles cannot contain the center point, we know from the N = 1 case that their areas can't exceed 1; moreover, there does exist a feasible triangle, as shown in 2(a) above. Thus a(O, Y) = 1 = a* for all Y.)

Here is a picture of one solution:


The way the N = 2 problem is stated, the problem is solved as long as we exhibit a single pair of obstacle points that minimizes the greatest possible area of a feasible triangle. It is interesting however to extend the problem by asking for all obstacle pairs (X*, Y*) satisfying a(X*, Y*) = a*. For example, if the obstacle points have Cartesian coordinates M(−0.001, 0) and N(+0.001, 0), then it would seem that a(M, N) = 1. What mathematical properties of continuity or connectedness does the set of optimal obstacles have? There are probably general theorems that bear on this question.

No comments: