_{1}, O

_{2}, and O

_{3}shown here, the greatest-area feasible triangle must have all three of its vertices on the boundary of the disk.

*N*= 400 example.)

In today's post, we'll (finally!) solve the problem of finding the greatest-area triangle that doesn't strictly contain O

_{1}, O

_{2}, and O

_{3}. 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.*

_{1}, …, X

_{N}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 A

_{1}as the projection of A through X

_{1}to the disk boundary on the other side, and define B

_{1}as the projection of B through X

_{1}to the disk boundary on the other side; and similarly for A

_{2}, …, A

_{N}and B

_{2}, …, B

_{N}.

If vertex C (also on the disk boundary, by hypothesis) were located inside the proper arc A

_{1}B

_{1}, then triangle ABC would contain obstacle X

_{1}. Conversely, if vertex C were not inside the proper arc A

_{1}B

_{1}, then triangle ABC would not contain obstacle X

_{1}. The same is true for any other obstacle, and hence triangle ABC strictly contains obstacle X

_{i}if and only if C belongs to the proper arc A

_{i}B

_{i}. The set of feasible locations for vertex C is therefore the complement of the union of all the proper arcs A

_{i}B

_{i}. 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.

_{1}, …, X

_{N}.

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 O

_{1}, O_{2}, and O_{3}. 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 O_{1}, O_{2}, and O_{3}. must have some side touching some obstacle point. Let's say without loss of generality that side AB touches O_{1}.
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 A

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 θ:

_{2}, A_{3}, B_{2}, B_{3}, 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 θ:

B

_{x}= cos θ [[1 −*a*_{0}^{2}cos^{2}θ]] −*a*_{0}sin θ cos θ
B

_{y}= cos θ [[1 −*a*_{0}^{2}cos^{2}θ]] +*a*_{0}cos^{2}θ
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, O_{1})
A

_{2}=*F*(A, O_{2})
A

_{3}=*F*(A, O_{3})
B

_{2}=*F*(B, O_{2})
B

_{3}=*F*(B, O_{3}).
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

If we simply graph the areas of triangles ABA

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.

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

_{2}, ABA_{3}, ABB_{2}, ABB_{3}, 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, O

Triangle ABA

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

_{2}, and O_{3}becoming collinear at around 26°—actually, 26.0016…°—a value we'll denote by θ*. At this angle, points A_{2}and A_{3}coincide, and the feasible triangles are ABQ, ABB_{3}, and ABA_{3}.Triangle ABA

_{3}is none other than the spotlight triangle, with area 0.828637…. The other two feasible triangles, ABB_{3}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, B

_{3}, B

_{2}, Q', A

_{3}, A

_{2}), and the feasible triangles are ABQ, ABB

_{3}, and ABA

_{2}. The figure shows the example of 17°.

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

3. For θ* < θ < 60°, the ordering is stable (B, Q, A, B

_{3}, B_{2}, Q', A_{2}, A_{3}), and the feasible triangles are ABQ, ABB_{3}, and ABA_{3}. 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….

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

4. At θ = 60°, A coincides with B

The feasible triangles for θ = 60° are none other than the spotlight triangle and the edge triangle, which (thanks to the particular choice of

5. For 60° < θ < 90°, the ordering is stable (B, A

_{3}and B coincides with A_{3}, making B, A, O_{1}, and O_{3}collinear, and giving nontrivial feasible triangles ABQ, ABB_{2}, and ABA_{2}.The feasible triangles for θ = 60° are none other than the spotlight triangle and the edge triangle, which (thanks to the particular choice of

*a*_{0}) have equal areas, namely the benchmark area 0.828637….5. For 60° < θ < 90°, the ordering is stable (B, A

_{3}, Q, B_{3}, A, B_{2}, Q', A_{2}), and the feasible triangles are ABA_{2}, ABA_{3}, ABB_{2}, and ABB_{3}.
Triangles ABA

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

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.

_{2}and ABA_{3}have equal areas 0.596…, and triangles ABB_{2}and ABB_{3}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 O**_{1}, O_{2}, or O_{3}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:

Post a Comment