areacoordinate systemstriangles
Given a finite set of 2-d points, I need to find the maximum area of triangle formed.
My solution steps :
Is my solution correct? If not, what could be the cases where it gives wrong result?
Suppose that the center of the circles did not lie on one of the altitudes of $\triangle ABC$ (as shown in gray). Then by leaving the base of that altitude alone and moving that altitude to the center, we increase the altitude, and thereby the area of the triangle (as shown in black).
$\hspace{3.5cm}$
Therefore, the orthocenter of the triangle must coincide with the center of the circles.
Consider the following diagram, in which $O$ is both the orthocenter of $\triangle ABC$ and the center of the circles:
$\hspace{3.5cm}$
$\triangle AOF$ is similar to $\triangle COD$, thus, $|\overline{OC}||\overline{OF}|=|\overline{OA}||\overline{OD}|$. Furthermore, $\triangle AOE$ is similar to $\triangle BOD$, thus, $|\overline{OA}||\overline{OD}|=|\overline{OB}||\overline{OE}|$. Therefore, define $$ p=|\overline{OC}||\overline{OF}|=|\overline{OA}||\overline{OD}|=|\overline{OB}||\overline{OE}|\tag{1} $$ and $$ a=|\overline{OA}|\quad b=|\overline{OB}|\quad c=|\overline{OC}|\tag{2} $$ With these definitions, we get $$ |\overline{OD}|=p/a\quad|\overline{OE}|=p/b\quad|\overline{OF}|=p/c\tag{3} $$ Note that $$ \frac{|\triangle AOB|}{|\triangle ABC|}=\frac{|\overline{OF}|}{|\overline{OF}|+|\overline{OC}|}=\frac{p}{p+c^2}\tag{4} $$ $$ \frac{|\triangle BOC|}{|\triangle ABC|}=\frac{|\overline{OD}|}{|\overline{OD}|+|\overline{OA}|}=\frac{p}{p+a^2}\tag{5} $$ $$ \frac{|\triangle COA|}{|\triangle ABC|}=\frac{|\overline{OE}|}{|\overline{OE}|+|\overline{OB}|}=\frac{p}{p+b^2}\tag{6} $$ and because $|\triangle AOB|+|\triangle BOC|+|\triangle COA|=|\triangle ABC|$, $(4)-(6)$ yield $$ \frac{p}{p+a^2}+\frac{p}{p+b^2}+\frac{p}{p+c^2}=1\tag{7} $$ Using $a=1$, $b=2$, and $c=3$, we can solve $(7)$ to get $p=1.458757077431284$.
Looking at the area of $\triangle AOB$ in two different ways, we get $$ \begin{align} 4|\triangle AOB|^2=|\overline{AB}|^2|\overline{OF}|^2&=(a^2+b^2-2ab\cos(\angle AOB))(p/c)^2\\ &=a^2b^2\sin^2(\angle AOB)\\ &=a^2b^2(1-\cos^2(\angle AOB))\tag{8} \end{align} $$ Solving $(8)$ for $\cos(\angle AOB)$ using the quadratic formula, and similarly for the other angles, yields $$ \cos(\angle AOB)=\frac{p^2-\sqrt{(p^2-c^2a^2)(p^2-b^2c^2)}}{abc^2}\tag{9} $$ $$ \cos(\angle BOC)=\frac{p^2-\sqrt{(p^2-a^2b^2)(p^2-c^2a^2)}}{a^2bc}\tag{10} $$ $$ \cos(\angle COA)=\frac{p^2-\sqrt{(p^2-a^2b^2)(p^2-b^2c^2)}}{ab^2c}\tag{11} $$ Using the equations above, we get
$$\angle BOC=104.071123766006501^\circ$$ $$|\triangle BOC|=2.909984011512956$$
$$\angle COA=119.094556197774592^\circ$$ $$|\triangle COA|=1.310727640381874$$
$$\angle AOB=136.834320036218908^\circ$$ $$|\triangle AOB|=0.684110332666474$$ Therefore, we get $$|\triangle ABC|=4.904821984561304$$
EDIT.
I'm inserting here a purely geometrical solution, the original reasoning can be seen at the end.
I'll repeatedly make use of the following result: if we have a line $r$ and an arc of circle $\gamma$, and the point $Q\in\gamma$ which is the farthest from $r$ is not an endpoint of $\gamma$, then the tangent at $Q$ is parallel to $r$.
The vesica piscis is composed of two arcs, with centers $O$ and $O'$. Let's consider the case when the vertices $ABC$ of an inscribed triangle are all internal points of the arcs: $A$ on arc $O$ and $BC$ on arc $O'$. If $ABC$ is the triangle of maximum area, then $B$ must be the point on the arc which is the farthest from line $AC$ and by the above result the tangent at $B$ must be parallel to $AC$, i.e. radius $O'B$ must be perpendicular to $AC$ and thus lies on an altitude of triangle $ABC$. By the same argument we also get $O'C\perp AB$, hence $O'C$ also lies on an altitude and $O'$ is the orthocenter of the triangle.
But we also have $OA\perp BC$, implying that altitude $OA$ must pass through $O'$, and that can happen only if $A=O'$. Triangle $ABC$ is then isosceles and right angled at $A$, as shown in figure below. Its area is: $$ area_1={1\over2}d^2. $$
Let's now consider the case when one of the vertices (e.g. $A$) lies at an endpoint of the arcs, while $B$ and $C$ are internal, each on a different arc as in figure below (it's easy to show that we don't get maximum area if $B$ and $C$ lie on the same arc). Moreover, let $A'$ be the other endpoint and $M$ the midpoint of $OO'$ (see figure below).
For the area to be maximum we need as before $O'B\perp AC$ and $OC\perp AB$. If we set $\alpha=\angle O'OC$ we can notice that triangles $OFD$ and $AFM$ have both a right angle and a pair of equal vertical angles, hence $\angle MAF=\angle DOF=\alpha$. Moreover, $\angle O'AC={1\over2}\angle O'OC={1\over2}\alpha$, because they are an inscribed and central angle subtending the same arc in circle $O'$.
We can analogously set $\alpha'=\angle OO'B$ to find: $\angle GAM=\alpha'$ and $\angle OAB={1\over2}\alpha'$. But $\angle OAM=\angle O'AM=30°$, hence we have: $$ \alpha+{1\over2}\alpha'=30° \quad\text{and}\quad \alpha'+{1\over2}\alpha=30°. $$ This system of equation can be easily solved to get: $$ \alpha=\alpha'=20°. $$
Hence the largest triangle in this case is isosceles and symmetric about line $AA'$. To compute its sides, note that from $\angle ABA'=120°$ we get $\angle BA'A=60°-\alpha$ and $AB=AC=2d\sin(60°-\alpha)$. Its area is then $$ area_2={1\over2}AB\cdot AC\cdot\sin(\alpha+\alpha')= {1\over2}\big(2d\sin(60°-\alpha)\big)^2\sin2\alpha= 2d^2\sin^340°\approx 0.53 d^2. $$
Finally, we can consider the case when two points (e.g. $A$ and $B$) lie on the endpoints of the arcs. In that case point $C$ must be either $O$ or $O'$, for the tangent at $C$ to be parallel to $AB$. The area of triangle $ABC$ is: $$ area_1={1\over2}d^2\sin120°={\sqrt3\over4}d^2. $$
In summary, the largest area occurs in the second case.
ORIGINAL REASONING.
Assume WLOG that points $A$ and $B$ are chosen on the right side of the vesica, while $C$ is on the left side (obviously we cannot have maximum area if all three points lie on the same side). For given positions of $A$ and $B$ we get the maximum area if the tangent at $C$ is parallel to $AB$, i.e. if $OC\perp AB$, where $O$ is the center of the right circle (see figure below).
Hence if we choose $C$ at will and some point $D$ on $OC$, points $A$, $B$ of the largest triangle will be the intersections between the left circle (of center $O'$) and the perpendicular to $OC$ at $D$. Note that point $D$ must be close enough to $O$ so that point $A$ won't lie past the intersection point of the circle.
Let $H$ be the projection of $O'$ on $AB$ and $d$ the radius of the circles. If we set $\alpha=\angle O'OC$ and $x=OD$, then by triangle similitude we get: $$ O'H:x=\left({d-{x\over\cos\alpha}}\right):{x\over\cos\alpha} $$ that is: $$ O'H=d\cos\alpha-x. $$ We can then find base $AB$ of the triangle: $$ AB=2\sqrt{d^2-O'H^2}=2\sqrt{d^2-(d\cos\alpha-x)^2}. $$ The area of triangle $ABC$ is then: $$ area={1\over2}AB\cdot CD=(d-x)\sqrt{d^2-(d\cos\alpha-x)^2}. $$ If $x$ is kept constant we get the largest area when $\cos\alpha$ has the lowest possible value, i.e. when $\alpha$ has the greatest possible value (note that $0\le\alpha\le60°$ and $\cos\alpha$ is then positive and decreasing). But the largest possible value is attained by $\alpha$ when point $A$ lies at the intersection of the circles: in the following we can then study only that case.
Let's suppose then that $A$ lies at an intersection of the circles and name $A'$ the other intersection point (see figure below). Note that $\angle A'AB=\alpha$ and $\angle ABA'=120°$, so that $\angle AA'B=60°-\alpha$. We can then compute: $$ AB=2d\sin(60°-\alpha). $$ From the equality $AB=2\sqrt{d^2-(d\cos\alpha-x)^2}$ we then get: $$ x=d\cos\alpha-d\cos(60°-\alpha) $$ and we we can finally write an expression for the area as a function of $\alpha$: $$ area={1\over2}AB\cdot (d-x)=d^2\sin(60°-\alpha) (1-\cos\alpha+\cos(60°-\alpha)). $$ Expanding, this can be rewritten as: $$ {area\over d^2}={\sqrt3\over2}\cos\alpha-{1\over2}\sin\alpha +\cos\alpha\sin\alpha-{\sqrt3\over4}. $$
Now we only need to show that the maximum of this expression is attained for $\alpha=20°$. Note that it vanishes for $\alpha=60°$ and $\alpha=-120°$, hence there must be an absolute maximum between those values, corresponding to a stationary point.
Differentiating the above expression with respect to $\alpha$ and equating the result to zero, we get the equation: $$ 2\cos^2\alpha-{1\over2}\cos\alpha-1={\sqrt3\over2}\sin\alpha. $$ Squaring both sides we obtain $$ (2\cos^2\alpha-{1\over2}\cos\alpha-1)^2={3\over4}(1-\cos^2\alpha), $$ that is: $$ 16c^4-8c^3-12c^2+4c+1=0, $$ where I set $c=\cos\alpha$. This equation has $c={1\over2}$ as solution, which doesn't correspond to an acceptable value for $\alpha$. Hence we can divide the l.h.s. by $2c-1$ to get an equivalent cubic equation: $$ 8c^3-6c-1=0. $$ But from the cosine triplication formula: $\cos3x=4\cos^3x-3\cos x$ we get: $$ 4\cos^320°-3\cos20°=\cos60°={1\over2} $$ implying that $c=\cos20°$ is a solution of the above equation. The other two solutions can be shown to be negative, hence the only acceptable stationary point is $\alpha=20°$, as it was to be proved.
Best Answer
A simple case of incorrect result:
We choose a million points around the unit circle.
We put three points very close together, but very far from the unit circle.
Those three points are what the algorithm would choose, but they would form a minuscule triangle.
When you can choose an equilateral triangle in the unit circle.
Or, better yet, you could choose a point in the far triangle and two points in the unit circle.