0
$\begingroup$

I have an algorithm that I think calculates the minimum radius of all points in the list, which runs in $O(n)$ time and is incredibly easy to implement, but is it correct? If so, has it been invented before? It is not described on Wikipedia.

The algorithm, given a list of all points with $x,y$-coordinates, is as follows:

  1. Get average of all $x$ and $y$ coordinates in the list in order to get the center of the circle $(\frac1n(x_1+x_2+\cdots+x_n), \frac1n(y_1+y_2+\cdots+y_n))$.
  2. Calculate the distance between all the points from the center using $d((x_1,y_1), (x_2,y_2)) = \sqrt{(x_2 − x_1)^2 + (y_2 − y_1)^2}$, to find the point with maximum distance from the average point. So, this distance will be the minimum radius to cover all points.
$\endgroup$
2
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Dec 5 '21 at 6:18
  • $\begingroup$ The algorithm you proposed sounds similar to the algorithm described in this question. $\endgroup$
    – VTand
    Dec 5 '21 at 6:27
6
$\begingroup$

Your algorithm is very simple because it doesn't always work.

Suppose we are given the points $(1,0)$, $(2,0)$, and $(6,0)$. Your algorithm will first average them to get the point $(3,0)$, then compute a maximum distance of $3$. However, a better solution is to take a circle with center $(3.5,0)$ and radius $2.5$.

$\endgroup$
3
  • $\begingroup$ In general, if you have a cluster of points close together, and a lone point far away, the proposed algorithm will give a center too close to the cluster. $\endgroup$
    – Mastrem
    Dec 5 '21 at 14:32
  • $\begingroup$ Yet it might be an interesting way to minimize the effect of outliers without the need to discriminate which points are outliers. $\endgroup$ Dec 5 '21 at 14:55
  • $\begingroup$ @A.I.Breveleri: No. If you want to minimize the effect of outliers, you need to remove them before running whatever algorithm you want. $\endgroup$
    – user21820
    Dec 5 '21 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.