Finding the 'three points'

Question

You are given $n$ points on the plane, no three of which are collinear. Therefore, there is always exactly one circle that passes through any three of the given points. Please choose any three points such that its corresponding circle encloses the $n$ points.

Let's say $S$ is the set of the $n$ points.

Also, one observation of the statement says: ''The problemsetter’s solution has cost $Θ(n)$."

The first algorithm I thought was:

1. Calculate the centroid $C$ of $S$.
2. Sort $S$ so that $S_i$ is further (squared Euclidean distance) from $C$ than $S_{i+1}$.
3. $\triangle S_0S_1S_2$ is the desired triangle.

Of course, this algorithm is incorrect.

This is a counterexample:

Any triangle can be formed with $S_0$, $S_1$ and $S_2$, in this case.

The second algorithm I thought was:

1. Calculate the centroid $C$ of $S$.
2. Obtain point $A$ so $d(A, C) \geq d(A, X)$, for all $X \in S$ ($A$ is the furthest point from $C$).
3. Obtain the furthest point to $A$ in $S - \{A\}$. This is $B$.
4. And then, find a point $C$ so that $d(C, A) + d(C, B)$ is maximum in $S-\{A, B\}$.
5. Triangle solution is $\triangle ABC$.

This solution is $\Theta(n)$ and seems correct. Of course, to seem correct means nothing.

Is my solution correct? If not, can you help me finding the algorithm that solves this problem? (Or, even better...) Can you give me a hint?

Answer 1

1. Find the smallest enclosing circle $\Gamma$ of the points by any algorithm, such as Welzl's algorithm (documented here for example). This can be done in linear time.
2. The boundary of $\Gamma$ must have either two or three points. These points also form part of our answer to the question.
   • If there are three points on the boundary, we are done.
   • If there are only two, the boundary points form a diameter. Choose the third point as the point not on $\Gamma$ for which the angle subtended by the diameter at that point is the smallest.* Again, this can be done in linear time.

*This always produces an enclosing circle. If a new circle $\Gamma'$ is formed from the diameter and the chosen third point X:

• The points on the other side of the diameter from X remain in $\Gamma'$.
• The rest of the points on the same side have larger subtended angles, which implies that they are within $\Gamma'$ as well.