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

Question

Estoy buscando el algoritmo que localice eficientemente 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 una entrada (milagrosa) de la lista de la latitud/longitud exacta de cada persona en la Tierra en un momento determinado.

Toma también como proporcionada una función $d(p_1, p_2)$ que devuelve la distancia en la superficie de la tierra entre $p_1$ y $p_2$ - 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?

Sin duda, una solución es calcular $d(\ldots)$ para cada par de personas en el globo, luego ordena la lista de distancias de cada persona en orden ascendente, toma el primer elemento de cada lista y ordénalos en orden descendente y toma el mayor. Pero eso implica $n(n-1)$ invocaciones de $d(\ldots)$ , $n$ tipos de $n-1$ y un último tipo de $n$ artículos. 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

El periódico Vaidya, Pravin M. , En $O(n \log n)$ algoritmo para el problema del vecino más próximo Discrete Comput. Geom. 4, No. 2, 101-115 (1989), ZBL0663.68058 da un $O(n \log n)$ algoritmo para el problema de "todos los vecinos más próximos": 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 desde $p$ a un punto de $S \setminus \{p\}$ . Entonces el "punto más solitario" es el punto $p$ que maximiza $m(p)$ . Así que su problema puede resolverse en $O(n \log n)$ tiempo, lo que está bastante bien.

(En caso de que no esté claro, estoy aplicando su algoritmo al conjunto de puntos vistos como viviendo dentro de $\mathbb{R}^3$ utilizando el hecho de que existe una relación de preservación del orden entre la distancia a lo largo de la esfera y la distancia en línea recta en $\mathbb{R}^3$ .)

Answer 2

Ideemos iterativamente un candidato, "la persona más solitaria hasta el momento", y en cada paso eliminemos a muchas personas que podemos ver que no están tan solas.

Elige a una persona al azar y calcula su "soledad". Como es la primera, es por defecto la persona más solitaria hasta el momento.

Ahora vamos a empezar a buscar un nuevo candidato. Elija una persona al azar, encontrar a todos dentro de la soledad de nuestro registro actual. O este conjunto está vacío, o no. Si está vacío, hemos encontrado una nueva persona más solitaria, calcular su soledad, y continuar. Si no, marcamos a todos los que están en esa bola como felices, lo que sólo significa que los eliminamos del conjunto de personas que muestreamos aleatoriamente (pero no de cualquier cálculo futuro de soledad).

Esto acaba por encontrar a la persona más solitaria.

Antes de pensar en lo eficiente que es esto, hagamos una optimización. Opcionalmente, finjamos que el mundo es un toroide (siguiendo una buena tradición; la Mecánica Clásica de Arnol'd hace esto en una nota a pie de página mientras habla de la previsión meteorológica). Como de costumbre, no es esencial.

Ahora, antes de empezar, ordena a todos en dos listas, una por latitud y otra por longitud. Ahora podemos utilizar esto para encontrar de forma eficiente a todo el mundo dentro de un radio determinado, sin tener que evaluar cada distancia por pares. También podemos mejorar el otro paso, calculando la soledad de un nuevo candidato.

Por último, pensándolo mejor, he decidido que calcular la complejidad de este algoritmo me parece demasiado trabajo ahora mismo :-)

Answer 3

Este problema se denomina "problema del círculo vacío más grande" en Geometría Computacional, y tiene un $O(n \log n)$ solución siempre que se le dé el casco convexo de los puntos y los diagramas de Voronoi correspondientes. Aquí hay un documento muy legible sobre el problema:

Schuster, M. (2008). El problema del círculo vacío más grande . En: Proceedings of the Class of 2008 Senior Conference, Computer Science Department, Swarthmore College (pp. 28-37).

Answer 4

Tal vez sea posible reformular su problema de modo que " valores atípicos basados en la distancia ".

Answer 5

Simplemente dividir los puntos en una malla de triangulos . toda la esfera , incluyendo los puntos de la superficie se puede dividir como tal si la poblacion llamese P es divisible por 3 . (he escrito una publicacion para los otros casos En Deutschen Mathematica vol 127.6 ) entonces para no describir cada kilobyte en ese documento , ahora se puede utilizar el cálculo sobre X cantidad de vectores espacios con cada vector una "distancia" de otra persona. U entonces puede encontrar el ****Maximum ***such triángulo (3 vectores )