Ancho cinético
Una estructura de datos de ancho cinético es una estructura de datos cinética que mantiene el ancho de un conjunto de puntos móviles. En 2D, el ancho de un conjunto de puntos es la distancia mínima entre dos líneas paralelas que contienen el conjunto de puntos en la franja entre ellas. Para 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 ancho de un conjunto de puntos que responda , sea compacta y eficiente .
Considere las líneas paralelas que contienen el punto establecido en la franja entre ellas y están separadas por una distancia mínima. Una de las líneas debe contener un borde del casco convexo, y la otra línea debe pasar por un punto c del casco convexo de modo que (a, c) y (b, c) sean pares antípodas . ab y c se conocen como un par borde-vértice antípoda. Considere el dual del conjunto de puntos. Los puntos se dualizan en líneas y el casco convexo de los puntos se dualiza en la envolvente superior e inferior .del conjunto de líneas. Los vértices del casco convexo superior se dualizan en segmentos en la envolvente 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 al que se dualiza el punto. Cuando se ven de esta manera dualizada, los pares de antípodas son pares de segmentos, uno del sobre superior y otro del inferior, con rangos x superpuestos. Ahora, los sobres superior e inferior se pueden ver como dos listas ordenadas x diferentes de intervalos no superpuestos. Si estas dos listas se fusionan, los pares de antípodas son las superposiciones en la lista fusionada. Si un paryc es un par antípoda borde-vértice, entonces el intervalo x para ayb deben intersecar el intervalo x para c. Esto significa que el punto final común de los intervalos x para ayb debe estar dentro del intervalo x para c.
Los puntos finales de ambos conjuntos de intervalos x se pueden mantener en una lista ordenada cinética . Cuando los puntos se intercambian, la lista de pares de borde-punto antípoda se actualiza adecuadamente. Las envolventes superior e inferior se pueden mantener utilizando la estructura de datos estándar para casco cinético convexo . La distancia mínima entre pares de borde-punto se puede mantener con un torneo cinético . Por lo tanto, utilizando un casco cinético convexo para mantener las envolventes superior e inferior, una lista ordenada cinética en estos intervalos para mantener los pares borde-vértice antípoda, y un torneo cinético para mantener el par de distancia mínima separada, el diámetro de un punto en movimiento establecido puede ser mantenido.