¿Cómo se encuentra la "persona más solitaria del planeta"?

Question

Estoy buscando el algoritmo que localice eficazmente a la "Persona más solitaria del planeta", donde "más solitaria" se define como:

Distancia mínima máxima a otra persona, es decir, la persona para la que la otra persona más cercana está más lejos.

Supongamos que se introduce una lista (ciertamente milagrosa) de la latitud/longitud exacta de cada persona en la Tierra en un momento determinado.

También toma como proporcionada una función d(p1, p2) que devuelve la distancia en la superficie de la tierra entre p1 y p2-- Sé que esto no es trivial, pero es "sólo geometría esférica" y no la parte importante (para mí) de la pregunta.

¿Cuál es la forma más eficaz de encontrar a la persona más solitaria?

Ciertamente, una solución es calcular d(...) para cada par de personas en el globo, luego ordenar la lista de distancias de cada persona en orden ascendente, tomar el primer elemento de cada lista y ordenarlos en orden descendente y tomar el mayor. Pero eso implica n*(n-1) invocaciones de d(...), n ordenaciones de n-1 elementos y una última ordenación de n elementos. La última vez que lo comprobé, n en este caso está en algún lugar al norte de seis mil millones, ¿verdad? ¿Así que podemos hacerlo mejor?

Answer 1

Este documento da un algoritmo de O(n log n) para el problema de "todos los vecinos más cercanos": dado un conjunto de puntos S, encontrar todos los valores m(p) donde p es un punto de S y m(p) es la distancia mínima de p a un punto de S \p}. Entonces el "punto más solitario" es el punto p que maximiza m(p). Así que tu problema se puede resolver en tiempo O(n log n), lo cual está bastante bien.

(Por si no queda claro, estoy aplicando su algoritmo al conjunto de puntos vistos como si vivieran dentro de R^3, utilizando el hecho de que existe una relación de conservación del orden entre la distancia a lo largo de la esfera y la distancia en línea recta en R^3).

Answer 2

Vamos a iterativamente llegar con un candidato, "el más solitario persona tan lejos", y en cada paso eliminar a un montón de gente a la que se puede ver no son tan solitaria.

Elige una persona al azar, y calcular su "soledad". Ya que eres la primera, que por defecto son las más solitarias de la persona hasta el momento.

Ahora vamos a iniciar la búsqueda de un nuevo candidato. Elige una persona al azar, encuentre todos dentro de la nuestra actual registro de la soledad. Este grupo está vacía o no. Si está vacío, hemos encontrado una nueva persona más solitaria, calcular su soledad, y continuar. De lo contrario, la marca de todo el mundo en la pelota, tan feliz, que solo significa que eliminarlos de la piscina de las personas que nos muestra al azar (pero no de cualquier cálculos de futuro de la soledad).

Esto finalmente se encuentra la persona más solitaria.

Antes de pensar en qué tan eficiente es este, vamos a hacer una optimización. Opcionalmente, pretender que el mundo es un toro (siguiendo una tradición fina; Arnol d de la Mecánica Clásica hace esto en una nota de pie de página al hablar sobre el pronóstico meteorológico). Como de costumbre, no es esencial.

Ahora, antes de comenzar, ordenar todo el mundo en dos listas, una por la latitud y la otra con la longitud. Ahora podemos usar esto para buscar de forma eficiente todo el mundo dentro de algunos radio, sin tener que evaluar todos los pares de distancia. También podemos mejorar el otro paso, el cálculo de la soledad de un nuevo candidato.

Finalmente, en el segundo de los pensamientos que he decidido que en realidad el trabajo de la complejidad de este algoritmo suena como mucho trabajo ahora. :-)

Answer 3

Esto se llama el "problema de círculo vacío más grande" en geometría computacional y tiene una solución de O (n log n) siempre que se le da el casco convexo de los puntos y los diagramas de Voronoi correspondientes. Hay un libro muy legible en el problema aquí.

Answer 4

Es posible reformular el problema para que se aplicarán algoritmos de "aislados basados en la distancia".

Answer 5

a dividir los puntos en una malla de triángulos. la esfera entera, incluyendo la superficie de puntos pueden ser divididos como tal si la población lo llama P es divisible por 3. (He escrito una publicación para los otros casos en Deutschen Mathematica Vol. 127.6) no para describir cada kilobyte en ese papel, ahora puede utilizar cálculo en X cantidad de espacios de vectores con cada vector a 'distancia' de otra persona. U a continuación puede encontrar la *** máximo *** tal triángulo (3 vectores)