Ordenar por distancia euclidiana

$S$ es un conjunto de puntos en un plano. Se da un punto aleatorio en el mismo plano. La tarea es ordenar todo por distancia euclidiana entre e . $x \notin S$ $y \in S$ $x$ $y$

Un enfoque sin cerebro es calcular distancias entre e para todos y luego ordenarlos usando cualquier algoritmo rápido. $x$ $y$ $y \in S$

¿Hay alguna forma de almacenar o preprocesar para que el proceso de clasificación sea más rápido? $S$

cg.comp-geom sorting Alex K.
fuente

Puede considerar una cuadrícula de tamaño apropiado y puntos de grupo por el cuadrado correspondiente (usando, por ejemplo, tabla hash). Luego, para ciertos pares de cuadrados, puede inferir que todos los puntos de un cuadrado están más lejos de

x

$x$ que todos los puntos de otro cuadrado. En la práctica, podría ayudar, supongo.

ilyaraz

El "enfoque sin cerebro" que usted estableció se ejecuta en el tiempo O (n log n), donde n es el número de puntos en S, que supongo que es bastante rápido en la práctica. ¿Desea eliminar el factor log n, o desea algo más, como la ordenación externa ?

Tsuyoshi Ito

El punto es que tengo un tiempo prácticamente ilimitado para preparar mi conjunto de puntos, pero el tiempo para ordenarlos es muy limitado. Dicho esto, se aprecia cualquier aceleración de la clasificación estándar, incluso si es la misma O (n log n), pero más rápida en el peor de los casos (o el mejor de los casos, o lo que sea).

Alex K.

Por ejemplo, si almaceno S como un árbol 2-d, puedo encontrar un vecino más cercano en el tiempo O (log n). Quizás haya una solución similar para mi tarea. No soy un gran experto en estructuras de datos espaciales, y hay tantos de ellos, que fácilmente podría perderlo.

Alex K.

Respuestas:

Solución 1: Encuentre las bisectrices perpendiculares entre pares de puntos y construya la disposición de estas líneas. La disposición tiene celdas , dentro de las cuales el orden ordenado es constante. Por lo tanto, cree una estructura de datos de ubicación de puntos para la disposición y decore cada celda con el orden ordenado que se devolverá para los puntos dentro de esa celda. Los pedidos ordenados entre celdas adyacentes difieren solo en una sola transposición, por lo que puede usar una estructura de datos persistente para permitir que las representaciones de estos pedidos clasificados compartan espacio. El espacio total es y el tiempo de consulta es $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

Solución 2: Elija una muestra aleatoria de de estas mismas bisectrices perpendiculares, construya su disposición y divida cada celda de disposición por segmentos de línea vertical a través de cada cruce de dos líneas muestreadas. La partición resultante tiene celdas , cada una de las cuales con alta probabilidad es cruzada por bisectrices sin muestrear. Decora cada celda de la partición mediante un orden ordenado válido de los puntos como se ve desde alguna x dentro de la celda. El espacio total es . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

Ahora, para hacer una consulta, ubique el punto de consulta en la partición, busque el orden almacenado con la celda de partición y use el algoritmo de clasificación de comparación de árbol cartesiano de Levcopoulos y Petersson (1989) comenzando con este orden almacenado. El tiempo para este paso es proporcional a donde es el número de puntos que están fuera de orden con el punto . Pero es (cada uno sin muestrear causas bisectrices a lo sumo uno fuera de orden par de puntos), por lo que el tiempo de consulta $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ también es . $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
fuente

PD: aquí hay una variante alternativa de la solución 2 que usa el mismo espacio y tiempo de consulta pero intercambia un algoritmo de preprocesamiento más complicado por un algoritmo de consulta más simple: 11011110.livejournal.com/233793.html

David Eppstein

¿Por qué

preprocesamiento cuando puede ordenar todos los

puntos de partida en el tiempo

y almacenar los resultados en una tabla hash usando el espacio

para una búsqueda constante?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Debido a que hay puntos de inicio

con diferentes órdenes de clasificación, no

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein

Probablemente no podrá escapar de momento en que lo corte; incluso las regiones de precomputación correspondientes a todas las posibles órdenes de clasificación podrían (creo) producir regiones y, por lo tanto, encontrar 'su' región mediante cualquier técnica de búsqueda significativa tomará tiempo. ( EDITAR: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(n))$ esto está absolutamente mal; ¡vea la excelente respuesta de David Eppstein para obtener más información!) Una forma útil de reducir la complejidad, por otro lado, especialmente si no necesita la clasificación completa de una vez, pero solo necesita poder extraer aleatoriamente el más cercano sobre la marcha - que podría ser a través de orden superior diagramas de Voronoi: extensiones de la celda de Voronoi estándar que acogen no sólo el vecino más cercano, pero, papel de Frank Dehne etc. segunda más cercana de k-vecino más cercano de búsqueda, http: //people.scs .carleton.ca / ~ dehne / publications / 2-02.pdf parece ser la referencia canónica; su página de inicio en http://www.dehne.carleton.ca/publications tiene otros documentos sobre diagramas de Voronoi que podrían ser útiles. $k$

Steven Stadnicki
fuente

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@David Creo que deberías hacer de esto una respuesta.

James King

Secundado - n! Me sentí mal mientras lo escribía, pero no pude ver un caso en contra. Enmendaré mi respuesta en breve para corregir eso, pero realmente me gustaría ver una respuesta más directa; ¡gracias!

Steven Stadnicki