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. (Again I take the extrema to exist; this seems safe given the closed and bounded features of the problem.)
Here is a summary of where things stand:
- For N = 1, placing the obstacle at the center of the disk results in a greatest feasible triangle area of 1. For any other location of the obstacle, there exists a feasible triangle of area greater than 1. Thus, the center of the disk is the unique solution to the N = 1 problem.
- For N = 2, placing one obstacle at the center of the disk and the other obstacle anywhere in the disk results in a greatest feasible triangle area of 1. For any other arrangement of the obstacles, there exists a feasible triangle of area greater than or equal to 1. Thus, the center of the disk and an arbitrarily located second point together represent a solution (not unique) to the N = 2 problem.
- For N = 3, placing the three obstacles in the locations we have been denoting O1, O2, and O3 results in a greatest feasible triangle area of 0.8286369…. Our conjecture, not yet proven, is that no arrangement of three obstacles results in a smaller value than this for the greatest feasible triangle area.
A more economical way to summarize is to generalize the notation we used in the N = 2 solution. 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 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 N points Xi* for which aN(X1*, …, XN*) = aN*.
Using this notation, our summary is:
- 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….
It's been a lot of work for just a handful of equations! Still, getting to these results has been fun, and has required growing amounts of insight about the optimization. Some of this likely generalizes to arbitrary numbers of obstacles in arbitrary locations—such as the idea that if you know two vertices in a greatest-area feasible triangle, then the third vertex has to be one of a finite number of possibilities.
I will keep thinking about the N = 3 problem, although it's hard not to cheat and start exploring N = 4. Would any of my readers like to make a conjecture for the best obstacles in the N = 4 case? I'll stay out of the way while you work on it. Email any thoughts to firstname.lastname@example.org.
A note about N = 3. The three obstacles O1, O2, and O3 are each a distance 0.32096… from the center of the disk. I have been using decimals and dot-dot-dot to express this distance, but it can also be expressed exactly as the real root of the cubic polynomial 5x3 − 4x2 + 7x − 2, namely
And the resulting greatest area (0.8286369…) can also be expressed exactly as the positive root of the polynomial 160000x6 − 265824x4 + 412857x2 − 209952, namely
To calculate these values, I first generalized the coordinates of O1, O2, and O3 to be functions of a variable radius r. Then I calculated the vertices of the spotlight triangle and the edge triangle in terms of r. Because the spotlight triangle and the edge triangle share a common base, the two triangles have equal areas when their altitudes are equal. The equal-altitude condition turns out to be equivalent to 5r3 − 4r2 + 7r − 2 = 0.
(Note, even Mathematica won't be able to solve the equal-altitude equation unless you are careful to orient your diagram so that the common base is horizontal. Doing so leads to much simpler expressions in r.)