I'm looking for the algorithm that efficiently locates the "loneliest person on the planet", where "loneliest" is defined as:
Maximum minimum distance to another person — that is, the person for whom the closest other person is farthest away.
Assume a (admittedly miraculous) input of the list of the exact latitude/longitude of every person on Earth at a particular time.
Also take as provided a function $d(p_1, p_2)$ that returns the distance on the surface of the earth between $p_1$ and $p_2$ – I know this is not trivial, but it's "just spherical geometry" and not the important (to me) part of the question.
What's the most efficient way to find the loneliest person?
Certainly one solution is to calculate $d(\ldots)$ for every pair of people on the globe, then sort every person's list of distances in ascending order, take the first item from every list and sort those in descending order and take the largest. But that involves $n(n-1)$ invocations of $d(\ldots)$, $n$ sorts of $n-1$ items and one last sort of $n$ items. Last I checked, $n$ in this case is somewhere north of six billion, right? So we can do better?
Best Answer
The paper Vaidya, Pravin M., An $O(n \log n)$ algorithm for the all-nearest-neighbors problem, Discrete Comput. Geom. 4, No. 2, 101-115 (1989), ZBL0663.68058 gives an $O(n \log n)$ algorithm for the "all-nearest-neighbors" problem: given a set of points $S$, find all the values $m(p)$ where $p$ is a point of $S$ and $m(p)$ is the minimum distance from $p$ to a point of $S \setminus \{p\}$. Then the "loneliest point" is the point $p$ which maximizes $m(p)$. So your problem can be solved in $O(n \log n)$ time, which is pretty good.
(In case it's not clear, I'm applying their algorithm to the set of points viewed as living inside $\mathbb{R}^3$, using the fact that there's an order-preserving relationship between distance along the sphere and straight-line distance in $\mathbb{R}^3$.)