Let's say I am given 5 separate points, on the coordinate plane.
How would I find the greatest distance between one point to another?
What I mean is not the distance between 2 points, but I want to go through each point and find the greatest distance.
Is there 1 simple formula to do this?
I hope I'm clear.
Best Answer
Although there is no known efficient algorithm (see Doug M's comment), there are simpler ways to solve it than by finding the Euclidean distance. In particular, we use the following properties of the norm:
Let $d^p_{i,j}$ be the p-norm distance between points $i$ and $j$ (if you want to be technical, it is the p-norm of the vector formed by subtracting those two points). Since I can't prove this in general let's restrict p to be 1 or 2. Then, if, for a given $i,j$ and an arbitrary $p$, $d^p_{i,j}$ is maximum, then it is maximum for all $p$.
Practically, this means that we can compute the 1-norm, which is much simpler. The 1-norm would just be:
$$d^1_{i,j} = |x_i-x_j| + |y_i - y_j|$$
So computationally you need to do two subtractions and potentially a negation, and a sum, rather than (with the 2-norm), two subtractions, a squaring, a sum, and a square root.
Look for the highest 1-norm, then compute only a single 2-norm.