Disco envolvente cinético más pequeño
Una estructura de datos de disco envolvente más pequeña cinética es una estructura de datos cinética que mantiene el disco envolvente más pequeño de un conjunto de puntos en movimiento.
En 2 dimensiones, la estructura de datos de disco envolvente más pequeña cinética más conocida utiliza la triangulación delaunay del punto más lejano del conjunto de puntos para mantener el disco envolvente más pequeño. [1] La triangulación de Delaunay del punto más lejano es el dual del diagrama de Voronoi del punto más lejano . Se sabe que si el punto más lejano de la triangulación delaunay de un conjunto de puntos contiene un triángulo acutángulo, la circunferencia circunscrita de este triángulo es el disco envolvente más pequeño. De lo contrario, el disco envolvente más pequeño tiene el diámetro del punto establecido como su diámetro. Así, manteniendo el diámetro cinéticodel conjunto de puntos, la triangulación de delaunay del punto más lejano, y tenga o no la triangulación de delaunay del punto más lejano un triángulo acutángulo, se puede mantener el disco envolvente más pequeño. Esta estructura de datos responde y es compacta, pero no local ni eficiente: [1]
La existencia de una estructura de datos cinética que tiene eventos es un problema abierto. [1]
El disco envolvente más pequeño de un conjunto de n puntos en movimiento puede aproximarse mediante una estructura de datos cinéticos que procesa eventos y requiere un tiempo total. [2]
En dimensiones superiores a 2, mantener eficientemente la esfera envolvente más pequeña de un conjunto de puntos móviles es un problema abierto. [1]