El par de puntos más cercano entre dos conjuntos, en 2D

Tengo dos conjuntos de puntos en el plano bidimensional. Quiero encontrar el par de puntos más cercano tal que , , y la distancia euclidiana entre sea lo más pequeña posible. ¿Cuán eficientemente se puede hacer esto? ¿Se puede hacer en tiempo, donde ? $S,T$ $s,t$ $s \in S$ $t \in T$ $s,t$ $O(n \log n)$ $n = |S|+|T|$

Sé que si me dan un solo conjunto , entonces es posible encontrar el par de puntos más cercano en el tiempo usando un algoritmo estándar de divide y vencerás . Sin embargo, ese algoritmo no parece generalizarse al caso de dos conjuntos, porque no hay conexión entre la distancia entre los dos puntos más cercanos dentro de o frente a la distancia entre los dos puntos más cercanos a través de esos conjuntos. $S$ $s,s' \in S$ $O(n \log n)$ $S$ $T$

Pensé en almacenar el conjunto en un árbol -d, luego para cada , usando una consulta de vecino más cercano para encontrar el punto más cercano en a . Sin embargo, el peor tiempo de ejecución de esto podría ser tan malo como el tiempo . Hay resultados que dicen que si los puntos de se distribuyen aleatoriamente, entonces el tiempo de ejecución esperado para cada consulta es , por lo que obtendríamos un algoritmo con el tiempo de ejecución esperado $T$ $k$ $s \in S$ $T$ $s$ $O(n^2)$ $T$ $O(\log n)$ $O(n \log n)$ si se nos garantizara que los puntos se distribuyen aleatoriamente, pero estoy buscando un algoritmo que funcione para cualquier colección de puntos (no necesariamente distribuidos aleatoriamente).

Motivación: un algoritmo eficiente sería útil para esta otra pregunta .

algorithms computational-geometry DW
fuente

Respuestas:

Sí, este puede ser el tiempo . Construir un diagrama de Voronoi de . Luego, para cada punto , encuentre en qué celda del diagrama de Voronoi está contenido. El centro de esa celda es el punto que está más cerca de . $O(n \log n)$ $T$ $s \in S$ $t \in T$ $s$

Puede construir un diagrama de Voronoi en tiempo , y cada consulta (encontrar la celda que contiene ) se puede hacer en tiempo , por lo que el tiempo total de ejecución es . $O(n \log n)$ $s$ $O(\log n)$ $O(n \log n)$

DW
fuente

Agradable, mucho más simple de lo que se me ocurrió :).

aelguindy

Buen enfoque! Sin embargo, los enlaces ayudarían, especialmente para el lado de consulta de las cosas. Podría encontrar una página de Wikipedia que muestra que el problema general de la ubicación del punto se puede resolver en el tiempo

, pero ¿hay una mejor manera para el caso especial de las células Voronoi? Mi búsqueda solo apareció esta respuesta , que lo hace de la manera

O (\log n)

$O(\log n)$

O (n)

$O(n)$

j_random_hacker

T

$T$

n = | S | + | T |

$n = |S| + |T|$

O (n)

$\mathcal{O}(n)$

n

$n$

O (n)

$O(n)$

\leq 6 n

$\le 6n$

Eso parece correcto a partir de esta pregunta en math.stackexchange.

Albjenow

$L^1$

$d$ $O(n \log^{d-1} n)$

$O(n \log n)$ $O(n \log^2 n)$

$S, T$ $S$ $-\delta_z$ $T$ $\delta_z$ $z$ $\delta_z$ $\delta_z$

aelguindy
fuente

P_{2}

$P_2$

p_{m}

$p_m$

P

$P$ $P$

q_{m}

$q_m$

Q

$Q$ $Q$

l

$l$

Enlace roto :(

Keerthana Gopalakrishnan