Una estructura de datos de par cinético más cercano es una estructura de datos cinética que mantiene el par de puntos más cercano , dado un conjunto P de n puntos que se mueven continuamente con el tiempo en un espacio métrico. Si bien se conocían muchos algoritmos eficientes en el caso estático, resultaron difíciles de cinética , [1] por lo que se desarrollaron nuevos algoritmos estáticos para resolver este problema.
El enfoque cinético más simple para el mantenimiento del par más cercano es usar variantes de las triangulaciones de Delaunay . [2]
Considere un hexágono y divídalo en seis triángulos equiláteros , y luego cree una triangulación de Delaunay basada en cada triángulo equilátero, ya que cada uno tiene una forma convexa. La unión de estas seis triangulaciones de Delaunay, llamado gráfico de Delaunay equilátero (EDG), es un supergráfico para el gráfico vecino más cercano (NNG); los extremos del borde con longitud mínima en EDG dan el par más cercano. Es sencillo mantener triangulaciones de Delaunay basadas en formas convexas. Dado el EDG a lo largo del tiempo, al crear un árbol de torneo cinético sobre los bordes del EDG, se puede mantener fácilmente el par más cercano.
Este par más cercano KDS es eficiente, sensible amortizado y compacto, pero en general no es local. El siguiente enfoque presenta un KDS local para el mantenimiento del par más cercano.
Si el espacio alrededor de un punto p se divide angularmente en seis "cuñas", cada una de 60 ° de ancho, el punto más cercano ap es el más cercano de los puntos más cercanos en cada una de las cuñas. El resto de este artículo se centrará en las cuñas "principales" (las bisecadas por el eje x), y los argumentos simétricos se aplicarán a las otras cuñas después de girar el plano ± 60 ° .
Se dice que los puntos pyq están " emparejados " si son los puntos más cercanos entre sí. Claramente, el par de puntos más cercano es un par emparejado.