Sunday, November 27, 2016

Points In A Circle Problem: Analyzing Scenario (iii)

Given three distinct obstacle points located anywhere inside the unit disk, we established previously 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 two obstacle points on them.

(iii) Each proper side has one obstacle point on it.

Previously we also investigated scenario (ii) for the particular case of the conjectured optimum trio of obstacle points—let's call these obstacle points O1, O2, O3 from now on. By an explicit calculation, we determined that for these particular obstacles, all triangles in scenario (ii) have area less than 0.828…, the area of the spotlight triangle (and the edge triangle). Thus, the global maximizer isn't in class (ii).

Today we'll investigate scenario (iii). This is an interesting scenario, because it relates to a famous set of problems about triangles inscribed in triangles. We won't use any of that machinery, however.

We'll handle scenario (iii) in three subcases:

(iii)(a). All three vertices of the triangle are in the interior of the disk.

(iii)(b). Exactly two vertices of the triangle are in the interior of the disk.

(iii)(c). Exactly one vertex of the triangle is in the interior of the disk.


Scenario (iii)(a). All three vertices of the triangle are in the interior of the disk.

Given triangle ABC with obstacles X on BC, Y on CA, and Z on AB, we can (for example) slide vertex B slightly along AB (away from A), and simultaneously slide vertex C slightly along CA (toward A), using obstacle X as a "hinge" of sorts.


The triangle remains feasible throughout the sliding operation, because the obstacles remain on the proper sides. We also notice that if X is not the midpoint of BC, then the area of the triangle does not remain stationary. If XB is longer than CX, then the area increase due to sliding B exceeds the area decrease due to sliding C. Hence, if ABC is a greatest-area feasible triangle, then X must be the midpoint of BC.

We could have performed the sliding operation using any obstacle point as the "hinge," thus each obstacle must be the midpoint of the side it belongs to. (That is, the obstacle triangle XYZ is the medial triangle of ABC.)

So far we've made no assumption about the obstacle points other than non-collinearity, but now let's specialize to the case of the conjectured optimum trio of obstacles. If O1 be the midpoint of BC, O2 be the midpoint of CA, and O3 be the midpoint of AB, it follows from the fact that O1O2O3 is equilateral that ABC is also equilateral.

Thus, if ABC is a greatest-area feasible triangle with one obstacle on each side, and if all three vertices of ABC are in the interior of the disk, then up to congruence, ABC could not be other than this triangle:


However, this triangle only has area 0.53529..., which is less than the spotlight and edge triangles (0.82863...). This shows that the global maximizer isn't in class (iii)(a).

Scenario (iii)(b). Exactly two vertices of the triangle are in the interior of the disk.

By reasoning similar to the above (using O1 as a hinge), O1 must be the midpoint of BC. This allows us to parametrize triangle ABC by a single variable—say, the angle θ in this diagram.



The length r is actually a function of θ because, given the value of θ, r is to be chosen so that CO2 and BO3, extended, meet on the boundary of the disk.

Here is an animation showing how the family of triangles evolves over the range of θ values (0 to 60 degrees).



It's clear from the animation that r(θ) grows too slowly to offset the rapid decrease in altitude that results from rotating the top side. Thus, it makes sense that the area numbers decrease throughout the motion.

At this point the natural thing to do would be to express the area of triangle ABC as a function of θ. However, I did not actually derive r(θ) or the coordinates of vertex A as functions of θ. (The graphics above were generated using a combination of explicit functions and a root-finding routine.) Instead of calculating the area of triangle ABC, I decided to bound the area by calculating instead the area of a larger region, G, consisting of triangles C*O1O2, B*O1O3, O1O2O3, and O2O3Q, where vertices C*, B*, and Q lie on the boundary of the disk as shown.


For any angle θ, triangle C*O1O2 exceeds triangle CO1O2 in area, triangle B*O1O3 exceeds triangle BO1O3 in area, and triangle O2O3Q exceeds triangle O2O3A in area (the altitude from O2O3 is as great as possible because Q is at the bottom of the disk).

The lengths O1C* and O1B* are the positive roots of the quadratic equation r2 ± 0.64197 sin(θ) r − 0.896982. These are easily expressed as functions of θ, r±(θ), which makes the area of region G easy to express in closed form:

area(G) = ½r+(θ)s sin(π/3 + θ) + ½r(θ)s sin(π/3 − θ) + const.,

where s = 0.555925… is the known side of equilateral triangle O1O2O3.

And here's a graph of area(G). The maximum value is 0.823….


Since area(G) ≤ 0.823… and since the area of triangle ABC is less than area(G), we have that the area of triangle ABC is less than 0.823…. That value in turn is less than the area of the spotlight and edge triangles (0.82863…), which shows that the global maximizer isn't in class (iii)(b).

Scenario (iii)(c). Exactly one vertex of the triangle is in the interior of the disk.

This family of possibilities is also parametrized by a single variable—say, the y-coordinate of vertex C, as shown in this animation:


By drawing a careful diagram and repeatedly applying of the law of cosines, the law of sines, and the angle sum of a triangle, I was able to solve triangle ABC in terms of the variable y.


The graph of the area function as a function of y agrees with the behavior illustrated in the animation.


The greatest area occurs at the maximum y value, at which point the triangle ABC is isosceles.


The best area in class (iii)(c), 0.645389…, is less than the area of the spotlight and edge triangles (0.82863…), which shows that the global maximizer isn't in class (iii)(c).

And that completes the analysis of scenario (iii), at least for the particular obstacles O1, O2, and O3.

Together with the previous analysis of scenario (ii), this leads to our conclusion for today:

Conclusion

For the three obstacles O1, O2, and O3, the greatest-area feasible triangle has all three of its vertices on the boundary of the disk.

No comments: