Sunday, December 4, 2016

Points In A Circle Problem: The Best Triangles for the Conjectured Best Obstacles

Previously we established that for the obstacles O1, O2, and O3 shown here, the greatest-area feasible triangle must have all three of its vertices on the boundary of the disk.




(This needn't be the case for larger numbers of obstacles, as suggested by this N = 400 example.)



In today's post, we'll (finally!) solve the problem of finding the greatest-area triangle that doesn't strictly contain O1, O2, and O3. Later on, I'll write another post summarizing where things stand for the Points In A Circle Problem as a whole.

The starting point for today generalizes an observation from the solution to the N = 1 problem, as follows:

If two vertices are known in a greatest-area feasible triangle, then the remaining vertex must be one of a finite number of possibilities.

To see this, let obstacle points X1, …, XN be given in any arrangement. (The figure below shows an example for N = 3.) Given two vertices A and B in a greatest-area feasible triangle ABC (recall that A and B are on the disk boundary by hypothesis), define A1 as the projection of A through X1 to the disk boundary on the other side, and define B1 as the projection of B through X1 to the disk boundary on the other side; and similarly for A2, …, AN and B2, …, BN.


If vertex C (also on the disk boundary, by hypothesis) were located inside the proper arc A1B1, then triangle ABC would contain obstacle X1. Conversely, if vertex C were not inside the proper arc A1B1, then triangle ABC would not contain obstacle X1. The same is true for any other obstacle, and hence triangle ABC strictly contains obstacle Xi if and only if C belongs to the proper arc AiBiThe set of feasible locations for vertex C is therefore the complement of the union of all the proper arcs AiBi. This is, itself, a set of (closed) arcs on the boundary. 

Now, given a segment AB in the disk, we maximize the area of a triangle on base AB by putting the third vertex as far as possible perpendicularly from AB, subject to whatever constraints operate.

For example, if the only constraint is that the triangle must belong to the disk, then we maximize the area of triangle ABC by making vertex C one of the two points Q and Q' on the disk boundary where the tangent to the boundary is parallel to AB. These points are locally furthest from base AB (measuring distances perpendicularly).



Note that diameter QQ' bisects chord ab, so that aQ is congruent to bQ and aQ' is congruent to bQ'. Triangles abQ and abQ' are both isosceles.

The feasible region for vertex C is a union of closed arcs. Suppose first that C is in the interior of one of these arcs. Then, we can slide C back and forth by a small amount within that arc.


By the altitude property, either the area of the triangle will increase and decrease to first order as C slides back and forth, or else vertex C occupies one of the two points Q, Q' on the boundary where the sliding motion runs parallel to AB and thus doesn't change the area to first order. But if triangle ABC is a greatest-area feasible triangle, then the area can't increase to first order by sliding vertex C. Therefore, if triangle ABC is a greatest-area feasible triangle, then C must be one of the two points Q and Q', or else an endpoint of one of the feasible arcs. This is a finite set of possibilities for vertex C, determined by A, B, and the obstacles X1, …, XN.

Next we generalize another observation from the N = 1 solution:

If a greatest-area feasible triangle doesn't have any obstacle points on its boundary, then the triangle is an inscribed equilateral triangle.

This observation is corollary of the previous one, since the only possibilities for the third vertex are the two special places where sliding the third vertex doesn't gain you any area. The upshot is that the triangle must be isosceles on each of its bases, and therefore equilateral.

With the two italicized conclusions in hand, we can specialize to the case of obstacles O1, O2, and O3. To begin with, an inscribed equilateral triangle is clearly infeasible for these obstacles, because it would contain all three obstacle points. Thus, a greatest-area feasible triangle for O1, O2, and O3. must have some side touching some obstacle point. Let's say without loss of generality that side AB touches O1.

This condition is enough to allow us to parametrize the space of possibilities by a single variable, say the angle θ in this diagram, which ranges from 0 to 90 degrees.


Given a θ value, A and B are determined, as are the finitely many possible candidates for the third vertex C. These candidates are denoted A2, A3, B2, B3, Q, and Q'. Here's an animation showing how the players move as the angle θ changes. Points leading to infeasible triangles are crossed out. 


For each angle θ, there are in principle six candidate triangles to consider. It isn't hard to determine their areas as explicit functions of θ. I began by writing the coordinates of vertex B as functions of θ:

Bx = cos θ [[1 − a02cos2 θ]] − a0 sin θ cos θ

By = cos θ [[1 − a02cos2 θ]] + a0 cos2 θ

where [[ … ]] stands for a radical (i.e., square root).

Then I defined a function on points as follows. For a point P on the boundary of the disk and a point X in the interior, let F(P, X) denote the point on the boundary obtained by projecting from P through X all the way to the boundary. This is a useful function because given vertex B, we can use the function F to generate all but two of the other points needed for the problem.

A = F(B, O1)
A2 = F(A, O2)
A3 = F(A, O3)
B2 = F(B, O2)
B3 = F(B, O3).

To generate the remaining two points, Q and Q', define the projection onto the disk boundary for points M ≠ 0 by G(M) = M/||M||. Then for θ < 90°, Q = G(½(A + B)) and Q' = G(−½(A + B)). For θ = 90°, set Q = (−1, 0) and Q' = (1, 0).

To obtain an explicit formula for F(P, X), solve the equation ||P + t(X − P)||2 = 1 for t (the equation is linear after you discard the root t = 0; don't forget that ||P|| = 1), and plug the result into ||P + t(X − P)|| to obtain

F(P, X) = P + 2(1 − X•P)||X − P||−2(X − P)

where X•P denotes the inner product. With this explicit expression for F, the coordinates of all the points can be calculated explicitly as functions of θ, and hence all the candidate triangle areas can also be calculated.

If we simply graph the areas of triangles ABA2, ABA3, ABB2, ABB3, ABQ, and ABQ' as functions of θ on a single set of axes, we get a complicated picture:


Some of these areas are quite large; however, the largest areas belong to infeasible triangles. In order to sort all this out, let's chunk the θ range into parts, each with their own state of affairs.

1. When you watched the animation, you might have noticed the three points A, O2, and O3 becoming collinear at around 26°—actually, 26.0016…°—a value we'll denote by θ*. At this angle, points A2 and A3 coincide, and the feasible triangles are ABQ, ABB3, and ABA3



Triangle ABA3 is none other than the spotlight triangle, with area 0.828637…. The other two feasible triangles, ABB3 and ABQ, have smaller areas (0.452… and 0.681…, respectively). 

So for θ = θ*, the best triangle is the spotlight triangle.


2. For 0 ≤ θ < θ*, the order of the points around the disk boundary is stable (B, Q, A, B3, B2, Q', A3, A2), and the feasible triangles are ABQ, ABB3, and ABA2. The figure shows the example of 17°.



Here is a graph of how the three feasible triangle areas vary over the range 0 ≤ θ < θ*.


Over this range, none of the feasible triangles reaches or exceeds the benchmark 0.828637… (shown as a dashed line).


3. For θ* < θ < 60°, the ordering is stable (B, Q, A, B3, B2, Q', A2, A3), and the feasible triangles are ABQ, ABB3, and ABA3. The figure shows the example of 48°.



Here is a graph of how the three feasible triangle areas vary over the range θ* < θ < 60°.



Over this range, none of the feasible triangles reaches or exceeds the benchmark 0.828637…. 


4. At θ = 60°, A coincides with B3 and B coincides with A3, making B, A, O1, and O3 collinear, and giving nontrivial feasible triangles ABQ, ABB2, and ABA2.



The feasible triangles for θ = 60° are none other than the spotlight triangle and the edge triangle, which (thanks to the particular choice of a0) have equal areas, namely the benchmark area 0.828637….


5. For 60° < θ < 90°, the ordering is stable (B, A3, Q, B3, A, B2, Q', A2), and the feasible triangles are ABA2, ABA3, ABB2, and ABB3.



Here is a graph of how the four feasible triangle areas vary over the range 60° < θ < 90°.


Over this range, none of the feasible triangles reaches or exceeds the benchmark 0.828637…. 


6. At θ = 90°, the feasible triangles are ABA2, ABA3, ABB2, and ABB3



Triangles ABA2 and ABA3 have equal areas 0.596…, and triangles ABB2 and ABB3 have equal areas 0.453…. None of them bests the benchmark 0.828637….


Altogether then, among feasible triangles over the entire θ range, the spotlight triangles and edge triangles are best. 

Conclusion

The triangle of greatest area that doesn't strictly contain any of the obstacles O1, O2, or O3 is either a spotlight triangle or an edge triangle, with area 0.828637….

This settles the question for these particular obstacles, and it provides an upper bound for the problem of placing three 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.

No comments: