Una estructura de datos de diámetro cinético es una estructura de datos cinéticos que mantiene el diámetro de un conjunto de puntos en movimiento. El diámetro de un conjunto de puntos en movimiento es la distancia máxima entre cualquier par de puntos en el conjunto. En el caso bidimensional, la estructura de datos cinéticos para el casco convexo cinético se puede utilizar para construir una estructura de datos cinéticos para el diámetro de un conjunto de puntos en movimiento que responda , sea compacto y eficiente .
El par de puntos con máxima distancia por pares debe ser uno de los pares de puntos antípodas del casco convexo de todos los puntos. Tenga en cuenta que dos puntos son puntos antípodas si tienen líneas de apoyo paralelas . En el caso estático, el diámetro de un conjunto de puntos se puede encontrar calculando el casco convexo del conjunto de puntos, encontrando todos los pares de puntos antípodas y luego encontrando la distancia máxima entre estos pares. Este algoritmo se puede cinetizar de la siguiente manera:
Considere el dual del conjunto de puntos. Los puntos se dualizan a líneas y el casco convexo de los puntos se dualiza a la envolvente superior e inferior del conjunto de líneas.. Los vértices del casco convexo superior se dualizan en segmentos en el sobre superior. Los vértices del casco convexo inferior se dualizan en segmentos en la envolvente inferior. El rango de pendientes de las líneas de apoyo de un punto en el casco se dualiza con el intervalo x del segmento con el que se dualiza el punto. Cuando se ven de esta manera dualizada, los pares de antípodas son pares de segmentos, uno de la envolvente superior, uno de la inferior, con rangos de x superpuestos. Ahora, las envolventes superior e inferior se pueden ver como dos listas diferentes ordenadas en x de intervalos que no se superponen. Si estas dos listas se fusionan, los pares de antípodas 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 se intercambian puntos, la lista de pares de antípodas se actualiza. Las envolventes superior e inferior se pueden mantener utilizando la estructura de datos estándar para casco convexo cinético . La distancia máxima entre pares de antípodas se puede mantener con un torneo cinético . Por lo tanto, utilizando un casco convexo cinético para mantener las envolventes superior e inferior, una lista ordenada cinética en estos intervalos para mantener los pares de antípodas y un torneo cinético para mantener el par de distancia máxima entre sí, se puede mantener el diámetro de un conjunto de puntos en movimiento. .