3
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ The new algorithm is not correct. Your counterexample shows what goes wrong here, as well. $A$ and $B$ will be the two points farthest away. If the line through them goes through the centroid, some of the points will be outside the circle no matter which third point you choose. $\endgroup$ Aug 22, 2016 at 20:49
  • $\begingroup$ If we imagine projecting all of the points to a sphere using stereographic projection, what we're looking for is three point such that the plane through them (a) passes below the north pole, and (b) passes (non-strictly) above all of the given points. This representation may be easier to work with because everything is now linear. $\endgroup$ Aug 22, 2016 at 22:16
  • $\begingroup$ I don't know if this will work: first you choose some points from $S$ such that they form a convex polygon which contains $S$, then you use the (unproved but seemingly true) result here. $\endgroup$
    – shardulc
    Aug 22, 2016 at 22:52

1 Answer 1

2
$\begingroup$
  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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .