¿Encuentra la distancia de puntos más corta por pares en o (n log n)?

El siguiente ejercicio ha sido entregado a los estudiantes que superviso:

Dados $n$ puntos en el plano, diseñe un algoritmo que encuentre un par de puntos cuya distancia sea mínima entre todos los pares de puntos. El algoritmo debe ejecutarse en el tiempo $o(n^2)$ .

Existe un algoritmo de división y conquista (relativamente) simple que resuelve la tarea a tiempo $\Theta(n \log n)$ .

Pregunta 1 : ¿Existe un algoritmo que resuelva el problema dado exactamente en el peor de los casos $\mathcal{o}(n \log n)$ ?

Lo que me hizo sospechar que esto podría ser posible es un resultado que recuerdo haber visto en alguna charla (referencia apreciada). Declaró algo en el sentido de que no se puede disponer más que un número constante $c \in \mathbb{N}$ de puntos en el plano alrededor de algún punto $p$ dentro de un círculo de radio $r \in \mathbb{R}$ , con $r$ la distancia mínima entre cualquiera de los dos puntos involucrados . Creo que $c=7$ , los puntos que forman un hexágono equilátero con $p$ en el centro (en el caso extremo).

En ese caso, el siguiente algoritmo debería resolver el problema en $n$ pasos.

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Observe que esto es (afirma que es) en el tiempo lineal porque sólo un número constante de puntos en rpuede ser no farer lejos que ma partir de p(suponiendo por encima de declaración); solo estos puntos tienen que ser investigados para encontrar un nuevo mínimo. Hay una trampa, por supuesto; ¿Cómo se implementa nextNeighbour(tal vez con preprocesamiento en tiempo lineal)?

$R$ $p \notin R$ $m \in \mathbb{R}$

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$ .

Suponga que es finito. ¿Es posible encontrar con una distancia mínima desde en tiempo (amortizado) ? (Puede suponer que se construye agregando puntos investigados uno por uno). $R_{p,m}$ $p' \in R_{p,m}$ $p$ $\mathcal{O}(1)$ $R$ $p$

ds.data-structures cg.comp-geom Rafael
fuente

Propondría buscar con el "par más cercano" como palabra clave.

Yoshio Okamoto

Todo esto es algo estándar por ahora, vea los dos primeros capítulos aquí: goo.gl/pLiEO

Sariel Har-Peled

PD. Si desea el tiempo esperado, incluso puede calcular la triangulación de Delaunay, que contiene la distancia mínima.

domotorp

Después de la pregunta 1, escribe "no se puede organizar un número constante de puntos en el plano alrededor de algún punto p dentro de un círculo de radio r, con r la distancia mínima entre p y cualquier otro punto". Esto ciertamente no es cierto: puede tomar cualquier número de puntos en el círculo de radio r. Su afirmación es cierta si r es la distancia mínima entre dos puntos, en cuyo caso la prueba es bastante simple.

domotorp

la primera pregunta es material de libros de texto, como ya se señaló: definitivamente no es nivel de investigación. No entiendo la segunda pregunta: ¿para cualquier , el que está pidiendo o bien no existe o es el vecino más cercano a en . Entonces, ¿cómo es esto diferente de la pregunta 1? ¿Sobre qué está amortizando?

m

$m$

p^{'}

$p'$

p

$p$

R

$R$

Sasho Nikolov el

Respuestas:

Es imposible resolver el problema en menos de tiempo en modelos estándar, por ejemplo, utilizando árboles de decisión algebraicos. Esto se desprende del trabajo de Yao y Ben-Or que muestra que en este modelo no es posible decidir si un conjunto de números de entrada son todos diferentes o no (ver http://people.bath.ac.uk/masnnv /Teaching/AAlg11_8.pdf ). En caso de su problema, imagine que todos ellos están en la línea real. Si dos puntos son iguales, entonces su salida sería dos puntos con distancia cero, mientras que de lo contrario no, por lo que una solución a su problema también resolvería el problema DISTINCT NUMBERS. Si desea suponer que todos sus puntos son diferentes, simplemente agregue a $cn\log n$ $n$ $i\epsilon$ $x_i$ entradas del problema DISTINCT NUMBERS, en este caso si su salida es como máximo , entonces los números no son todos distintos. (Aunque en este caso tiene que usar una versión prometedora donde la diferencia de dos números distintos es al menos , pero creo que la misma prueba funciona para mostrar que también necesita en este caso.) $n\epsilon$ $2n\epsilon$ $\Omega(n\log n)$

domotorp
fuente

De hecho, gracias. Eso responde a la pregunta 2 (negativamente), también.

Raphael

Aparentemente, el problema que menciona también se conoce como Problema de distinción de elementos .

Raphael el

La referencia de @Sariel Har-Peled ( goo.gl/pLiEO ) presenta un algoritmo práctico de tiempo lineal para encontrar el par más cercano. Ese documento aborda directamente este argumento y explica que no se aplica porque el algoritmo utiliza un modelo de cálculo más potente.

Kevin Cline

Sí, pero la pregunta pedía específicamente el peor tiempo de ejecución. Pero estoy de acuerdo en que todas mis observaciones aparecen ya en la tesis de Sariel.

domotorp

Hay un algoritmo de tiempo esperado lineal aleatorio de Rabin; ver, por ejemplo, Rabin lanza una moneda en el blog de Lipton.

David Eppstein
fuente

Por mucho que entiendo la pregunta 2, el algoritmo de Rabin proporciona una especie de respuesta a eso también. En cada paso de tiempo, la estructura de datos es una cuadrícula con un ancho de celda menor que la distancia más pequeña entre pares de puntos vistos hasta ahora, dividido por (para que ninguna celda contenga más de un solo punto). Para responder la consulta en la pregunta 2, solo necesita asignar a una celda en la cuadrícula y observar un número constante de celdas a su alrededor. Mediante el análisis del algoritmo, si el conjunto de puntos de entrada se examina en orden aleatorio, entonces el tiempo de actualización amortizado para la cuadrícula es por nuevo punto en expectativa. $\sqrt{2}$ $p$ $O(1)$

Sasho Nikolov
fuente

Por cierto, no me refiero a la versión del algoritmo como lo describe Lipton, sino como se describe en el primer comentario (y el libro de Kleinberg y Tardos).

Sasho Nikolov el

Solo con expectativa, ver la respuesta de domotorps.

Raphael

No veo en ningún lado que quisieras restringirte a algoritmos deterministas. El algoritmo de Rabin es interesante precisamente porque rodea los límites inferiores del árbol de decisión (esto es similar a los límites inferiores para los algoritmos de clasificación de comparación frente a los de clasificación de enteros). por cierto, probablemente hay más que rabin usa para rodear el límite inferior, a saber, el truco de hash utilizado para acceder a la cuadrícula

Sasho Nikolov el

Re el "más que usa Rabin": también la capacidad de redondear entradas de números reales a enteros. Hay que tener mucho cuidado con esto: si configura un modelo de cálculo en el que se pueden realizar operaciones aritméticas estándar y redondear números reales, todo en tiempo constante por operación, entonces es posible resolver problemas completos de PSPACE en tiempo polinómico en este modelo Pero Rabin solo redondea los números de entrada (a diferentes niveles de precisión en diferentes iteraciones), y esta forma circunscrita de redondeo no es problemática.

David Eppstein

@SashoNikolov Estaba buscando el peor momento en , así que también el peor de los casos en la pregunta 2. Esto no tiene nada que ver con si el algoritmo es determinista. No estoy seguro de qué sucede si combina el tiempo esperado y amortizado.

o (n \log n)

$o(n \log n)$

O (1)

$O(1)$

Raphael