circles and triangles problem

Question

I have an interesting problem here I've been trying to solve for the last little while:

I have 3 circles on a 2D xy plane, each with the same known radius. I know the coordinates of each of the three centers (they are arbitrary and can be anywhere).

What is the largest triangle that can be drawn such that each vertex of the triangle sits on a separate circle, what are the coordinates of those verticies?

I've been looking at this problem for hours and asked a bunch of people but so far only one person has been able to suggest a plausible solution (though I have no way of proving it).

The solution that we have come up with involves first creating a triangle about the three circle centers. Next we look at each circle individually and calculate the equation of a line that passes through the circle's center and is perpendicular to the opposite edge. We then calculate two intersection points of the circle. This is then done for the next two circles with a result of 6 points. We iterate over the 8 possible 3 point triangles that these 6 points create (the restriction is that each point of the big triangle must be on a separate circle) and find the maximum size.

The results look reasonable (at least when drawn out on paper) and it passes the special case of when the centers of the circles all fall on a straight line (gives a known largest triangle). Unfortunate i have no way of proving this is correct or not.

I'm wondering if anyone has encountered a problem similar to this and if so, how did you solve it?

Note: I understand that this is mostly a math question and not programming, however it is going to be implemented in code and it must be optimized to run very fast and efficient. In fact, I already have the above solution in code and tested to be working, if you would like to take a look, please let me know, i chose not to post it because its all in vector form and pretty much impossible to figure out exactly what is going on (because it's been condensed to be more efficient).

Lastly, yes this is for school work, though it is NOT a homework question/assignment/project. It's part of my graduate thesis (abet a very very small part, but still technically is part of it).

Thanks for your help.

Edit: Heres a new algorithm that i came up with a little while ago.

Starting at a circle's centre, draw a line to the other two centres. Calculate the line that bisects the angle created and calculate the intersections between the circle and the line that passes through the centre of your circle. You will get 2 results. Repeat this for the other two circles to get a total of 6 points. Iterate over these 6 points and get 8 possible solutions. Find the maximum of the 8 solutions.

This algorithm will deal with the collinear case if you draw your lines in one "direction" about the three points.

From the few random trials i have attempted using CAD software to figure out the geometries for me, this method seems to outperform all other methods previously stated However, it has already been proven to not be an optimal solution by one of Victor's counter examples.

I'll code this up tomorrow, for some reason I've lost remote access to my university computer and most things are on it.

Answer 1

I've taken the liberty of submitting a second answer, because my original answer referred to an online app that people could play with to get insight. The answer here is more a geometric argument.

The following diagram illuminates, I hope, what is going on. Much of this was inspired by @Federico Ramponi's observation that the largest triangle is characterized by the tangent at each vertex being parallel to the opposite side.

_{(source: brainjam.ca)}

The picture was produced using a trial version of the excellent desktop program Geometry Expressions. The diagram shows the three circles centered at points A,E, and C. They have equal radii, but the picture doesn't really depend on the radii being equal, so the solution generalizes to circles of different radii. The lines MN, NO, and OM are tangent to the circles, and touch the circles at the points I,H, and G respectively. The latter points form the inner triangle IHG which is the triangle whose size we want to maximize.

There is also an exterior triangle MNO which is homethetic to the interior triangle, meaning that its sides are parallel to that of IHG.

@Federico observed that IHG has maximal area because moving any of its vertices along the corresponding circle will result an a triangle that has the same base but less height, therefore less area. To put it in slightly more technical terms, if the triangle is parameterized by angles t1,t2,t3 on the three circles (as pointed out by @Charles Stewart, and as used in my steepest descent canvas app), then the gradient of the area w.r.t to (t1,t2,t3) is (0,0,0), and the area is extremal (maximal in the diagram).

So how is this diagram computed? I'll admit in advance that I don't quite have the full story, but here's a start. Given the three circles, select a point M. Draw tangents to the circles centered at E and C, and designate the tangent points as G and I. Draw a tangent OHN to the circle centered at A that is parallel to GI. These are fairly straightforward operations both algebraically and geometrically.

But we aren't finished. So far we only have the condition that OHN is parallel to GI. We have no guarantee that MGO is parallel to IH or that MIN is parallel to GH. So we have to go back and refine M. In an interactive geometry program it's no big deal to set this up and then move M until the latter parallel conditions are met (by eyeballs, anyways). Geometry Expressions created the diagram, but I used a bit of a cheat to get it to do so, because its constraint solver was apparently not powerful enough to do the job. The algebraic expressions for G, I, and H are reasonably straightforward, so it should be possible to solve for M based on the fact that MIHG is a parallelogram, either explicitly or numerically.

I should point out that in general if you follow the construction starting from M, you have two choices of tangent for each circle, and therefore eight possible solutions. As in the other attempted answers to the question, unless you have a good heuristic to help you choose in advance which of the tangents to compute, you should probably compute all eight possible triangles and find the one with maximum area. The other seven will be extremal in the sense of being minimal area or saddle points.

That's it. This answer is not quite complete in that it leaves the final computation of M somewhat open ended. But it's reduced to either a 2D search space or the solution of an ornery but not humongous equation.

Finally, I have to disagree with @Federico's conclusion that this confirms that the solution proposed by the OP is optimal. It's true that if you draw perpendiculars from the circle centers to the opposite edge of the inner triangle, those perpendiculars intersect the circle to give you the triangle vertex. E.g. H lies on the line through A perpendicular to GI), but this is not the same as in the original proposed solution (which was to take the line through A and perpendicular to EC - in general EC is not parallel to GI).