Triangulación cinética

La triangulación de Delaunay parece una candidata natural, pero un análisis riguroso del peor caso del número de cambios discretos que ocurrirán en la triangulación de Delaunay (eventos externos) se consideró un problema abierto hasta 2015; ^{[ 3 ]} ahora se ha acotado a entre${\displaystyle \Omega (n^{2})}$^{[ 4 ]} y${\displaystyle O(n^{2+\epsilon })}$. ^{[ 5 ]}

Existe una estructura de datos cinética que mantiene eficientemente la triangulación de Delaunay de un conjunto de puntos móviles, ^{[ 6 ]} en la que la relación entre el número total de eventos y el número de eventos externos es${\displaystyle O(1)}$.

Kaplan et al. desarrollaron un esquema de triangulación aleatoria que experimenta un número esperado de${\displaystyle O(n^{2}\beta _{s+2}(n)\log ^{2}n)}$eventos externos, donde${\displaystyle s}$es el número máximo de veces que cada triplete de puntos puede volverse colineal,${\displaystyle \beta _{s+2}(q)={\frac {\lambda _{s+2}(q)}{q}}}$, y${\displaystyle \lambda _{s+2}(q)}$es la longitud máxima de una secuencia de Davenport-Schinzel de orden s + 2 en n símbolos. ^{[ 1 ]}

Existe una estructura de datos cinéticos (debido a Agarwal et al.) que mantiene una pseudotriangulación en${\displaystyle O(n^{2}2^{\sqrt {\log n\log \log n}})}$eventos totales. ^{[ 7 ]} Todos los eventos son externos y requieren${\displaystyle O(\lg n)}$tiempo de procesamiento.