Diámetro cinético (datos)

Una estructura de datos de diámetro cinético es aquella que mantiene el diámetro de un conjunto de puntos móviles. El diámetro de un conjunto de puntos móviles es la distancia máxima entre cualquier par de puntos del conjunto. En el caso bidimensional, la estructura de datos cinético para la envolvente convexa cinética se puede utilizar para construir una estructura de datos cinético para el diámetro de un conjunto de puntos móviles que sea sensible , compacta y eficiente .

El par de puntos con la máxima distancia entre pares debe ser uno de los pares de puntos antipodales de la envoltura convexa de todos los puntos. Cabe señalar que dos puntos son antipodales si tienen líneas de soporte paralelas . En el caso estático, el diámetro de un conjunto de puntos se puede calcular determinando la envoltura convexa del conjunto, encontrando todos los pares de puntos antipodales y, posteriormente, hallando la distancia máxima entre estos pares. Este algoritmo se puede cinetizar de la siguiente manera:

Consideremos el dual del conjunto de puntos. Los puntos se dualizan en líneas y la envoltura convexa de los puntos se dualiza en la envolvente superior e inferior del conjunto de líneas . Los vértices de la envoltura convexa superior se dualizan en segmentos de la envolvente superior. Los vértices de la envoltura convexa inferior se dualizan en segmentos de la envolvente inferior. El rango de pendientes de las líneas de soporte de un punto en la envoltura se dualiza en el intervalo x del segmento al que se dualiza dicho punto. Vistos de esta forma dualizada, los pares antipodales son pares de segmentos, uno de la envolvente superior y otro de la inferior, con rangos x superpuestos. Ahora bien, las envolventes superior e inferior pueden verse como dos listas diferentes ordenadas por x de intervalos no superpuestos. Si estas dos listas se fusionan, los pares antipodales son las superposiciones en la lista fusionada.

Las superposiciones en la lista fusionada de intervalos x se pueden mantener almacenando los puntos finales de los intervalos en una lista ordenada cinética . Cuando los puntos se intercambian, la lista de pares antipodales se actualiza. Las envolventes superior e inferior se pueden mantener utilizando la estructura de datos estándar para la envoltura convexa cinética . La distancia máxima entre pares antipodales se puede mantener con un torneo cinético . Por lo tanto, utilizando la envoltura convexa cinética para mantener las envolventes superior e inferior, una lista ordenada cinética en estos intervalos para mantener los pares antipodales y un torneo cinético para mantener el par de máxima distancia entre sí, se puede mantener el diámetro de un conjunto de puntos en movimiento.

Esta estructura de datos es receptiva , compacta y eficiente . La estructura de datos utiliza${\displaystyle O(n)}$espacio porque la envoltura convexa cinética, la lista ordenada y las estructuras de datos de torneo utilizan${\displaystyle O(n)}$espacio. En todas las estructuras de datos, los eventos, inserciones y eliminaciones se pueden manejar en${\displaystyle O(\log ^{2}n)}$tiempo, por lo que la estructura de datos es receptiva, lo que requiere${\displaystyle O(\log ^{2}n)}$por evento. La estructura de datos es eficiente porque el número total de eventos es${\displaystyle O(n^{2+\epsilon })}$a pesar de${\displaystyle \epsilon >0}$y el diámetro de un conjunto de puntos puede cambiar${\displaystyle \Omega (n^{2})}$veces, incluso si los puntos se mueven linealmente. Esta estructura de datos no es local porque un punto puede estar en muchos pares antipodales y, por lo tanto, aparecer muchas veces en el torneo cinético.

La existencia de una estructura de datos cinéticos locales para el diámetro es una cuestión abierta.

Mantener de forma eficiente el diámetro cinético de un conjunto de puntos en dimensiones superiores a 2 es un problema abierto . La envolvente convexa cinética eficiente en dimensiones superiores a 2 también es un problema abierto. ^{[ 1 ]}

• Ancho cinético
• Caja mínima cinética