22
$\begingroup$

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?

$\endgroup$
4
  • 11
    $\begingroup$ Russell Munroe, creator of xkcd, has a chapter, Loneliest Human, in his book, What If. He tries to answer, "What is the farthest one human being has ever been from every other living person?" He nominates the Apollo astronauts who stayed in lunar orbit during a Moon landing, possibly a lone Polynesian sailor, and the last surviving member of Scott's Antarctic expedition. $\endgroup$ Oct 4, 2014 at 23:33
  • 3
    $\begingroup$ @GerryMyerson, I think he goes by Randall now. $\endgroup$ Oct 5, 2014 at 8:33
  • 1
    $\begingroup$ @The, yes, I don't know what I was thinking. Randall it is. $\endgroup$ Oct 5, 2014 at 11:12
  • $\begingroup$ The chapter in Munroe's book is derived from a blog post: what-if.xkcd.com/72 $\endgroup$ Mar 22, 2022 at 19:16

5 Answers 5

29
$\begingroup$

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$.)

$\endgroup$
2
  • $\begingroup$ Could you please describe more that distance on sphere vs 3D distance relationship? $\endgroup$
    – Somnium
    Mar 7, 2022 at 19:34
  • 2
    $\begingroup$ @Somnium:consider any two points on the sphere. Then both their shortest distance-geodesic on the sphere's surface and their geodesic in three-space lie on the plane defined by the two points and the center of the sphere. (Unless the points are antipodal, in which case the relationship still holds). It's not hard to see that the 3-space distance is an increasing function of the surface distance; the latter is essentially just the angle measure $\theta$ spanned by the two points WRT the center, and the former is $2\sin(\theta/2)$. $\endgroup$ Mar 8, 2022 at 0:43
8
$\begingroup$

Let's iteratively come up with a candidate, "the loneliest person so far", and at each step weed out lots of people who we can see aren't as lonely.

Pick a person at random, and calculate their "loneliness". Since they're the first, they are by default the loneliest person so far.

Now let's start searching for a new candidate. Pick a person at random, find everyone within the our current record loneliness. Either this set is empty, or not. If it's empty, we've found a new loneliest person, calculate their loneliness, and continue. Otherwise, mark everyone in that ball as happy, which just means we remove them from the pool of people we sample randomly (but not from any future calculations of loneliness).

This eventually finds the loneliest person.

Before we think about how efficient this is, let's make an optimisation. Optionally, pretend the world is a torus (following a fine tradition; Arnol'd's Classical Mechanics does this in a footnote while talking about weather forecasting). As usual, it's not essential.

Now, before we begin, sort everyone into two lists, one by latitude and one by longitude. We can now use this to efficiently find everyone within some radius, without having to evaluate every pair-wise distance. We can also improve the other step, calculating the loneliness of a new candidate.

Finally, on second thoughts I've decided that actually working out the complexity of this algorithm sounds like too much work right now. :-)

$\endgroup$
0
7
$\begingroup$

This is called the "largest empty circle problem" in Computational Geometry, and has an $O(n \log n)$ solution provided that you are given the convex hull of the points and the corresponding Voronoi diagrams. Here is a very readable paper on the problem:

Schuster, M. (2008). The largest empty circle problem. In: Proceedings of the Class of 2008 Senior Conference, Computer Science Department, Swarthmore College (pp. 28-37).

$\endgroup$
1
  • $\begingroup$ I don't see how it is the same problem. The OP is, in effect, asking for a person such that a circle centered at the person and containing no other persons is as large as possible. The largest empty circle, in contrast, is a circle that contains no persons. If you find an empty circle, you haven't found a lonely person. $\endgroup$ Mar 22, 2022 at 12:05
2
$\begingroup$

It may be possible to reformulate your problem so that "distance-based outlier" algorithms will apply.

$\endgroup$
0
0
$\begingroup$

just divide the points into a mesh of triangles . the entire sphere , including the surface points can be divided as such if the population call it P is divisible by 3 . (I have written a publication for the other cases In Deutschen Mathematica vol 127.6 ) then not to describe every kilobyte in that paper, you can now use calculus on X amount of vectors spaces with each vector a 'distance' from another person. U then can find the ****Maximum ***such triangle (3 vectors )

$\endgroup$
1
  • 1
    $\begingroup$ If you have explicit references to the literature that would help, it would be much better to give them in full. (We encourage users to use their actual names anyway, although it's of course not a requirement.) $\endgroup$
    – Todd Trimble
    Sep 8, 2015 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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