Diámetro (geometría computacional)

En geometría computacional , el diámetro de un conjunto finito de puntos o de un polígono es su diámetro como conjunto , la mayor distancia entre dos puntos cualesquiera. El diámetro siempre se alcanza mediante dos puntos de la envoltura convexa de la entrada. Se puede utilizar una búsqueda por fuerza bruta trivial para encontrar el diámetro de${\displaystyle n}$puntos en el tiempo${\displaystyle O(n^{2})}$(suponiendo evaluaciones de distancia en tiempo constante), pero es posible utilizar algoritmos más rápidos para puntos en dimensiones bajas.

En dos dimensiones , el diámetro se puede obtener calculando la envoltura convexa y luego aplicando el método de los calibradores giratorios . Esto implica encontrar dos líneas de soporte paralelas para la envoltura convexa (por ejemplo, líneas verticales que pasan por los dos vértices con mínimo y máximo) .${\displaystyle x}$-coordenada) y luego rotando las dos líneas a través de una secuencia de pasos discretos que las mantienen como líneas de soporte paralelas hasta que hayan vuelto a su orientación original. El diámetro es la distancia máxima entre cualquier par de vértices de la envoltura convexa encontrados como los dos puntos de contacto de las líneas paralelas en este barrido. El tiempo para este método está dominado por el tiempo de construcción de la envoltura convexa:${\displaystyle O(n\log n)}$para un conjunto finito de${\displaystyle n}$puntos o tiempo${\displaystyle O(n)}$para un polígono simple con${\displaystyle n}$vértices. ^{[ 1 ]}

Para un conjunto dinámico de puntos bidimensionales sujeto a inserciones y eliminaciones de puntos, se puede mantener en el tiempo una aproximación al diámetro, con una razón de aproximación que se puede elegir arbitrariamente cercana a uno.${\displaystyle O(\log ^{2}n)}$por operación. ^{[ 2 ]} El diámetro exacto se puede mantener dinámicamente en el tiempo esperado.${\displaystyle O(\log n)}$por operación, en un modelo de entrada en el que el conjunto de puntos a insertar y eliminar, y el orden de las operaciones de inserción y eliminación, es el peor caso, pero el punto elegido para insertar o eliminar en cada operación se elige aleatoriamente del conjunto dado. ^{[ 3 ]}

Para un conjunto de puntos bidimensionales dinámicos de un tipo diferente,${\displaystyle n}$puntos que se mueven linealmente con velocidades fijas, el tiempo en el que los puntos alcanzan su diámetro mínimo y el diámetro en ese momento se pueden calcular en tiempo${\displaystyle O(n\log ^{2}n)}$^{[ 4 ]}

En tres dimensiones, el diámetro de un conjunto de puntos puede calcularse nuevamente en el tiempo.${\displaystyle O(n\log n)}$. ^{[ 5 ] [ 6 ]} Un método aleatorio para hacer esto por Clarkson y Shor utiliza como subrutina un algoritmo incremental aleatorio para encontrar la intersección de esferas congruentes. El algoritmo elige repetidamente un punto de entrada aleatorio, encuentra la distancia más lejana${\displaystyle \rho }$Desde ella, interseca esferas con radio${\displaystyle \rho }$centrado en cada punto, y elimina los puntos contenidos en la intersección resultante. Los puntos eliminados están dentro de la distancia${\displaystyle \rho }$de todos los demás puntos y, por lo tanto, no puede formar parte de ningún par con una distancia mayor que${\displaystyle \rho }$Cada punto se elimina cuando la distancia más lejana desde él es menor o igual a${\displaystyle \rho }$, la distancia más lejana desde el punto elegido al azar, que ocurre con probabilidad${\displaystyle {\tfrac {1}{2}}}$, por lo que se elimina la mitad de los puntos en promedio en cada iteración del algoritmo. El tiempo total esperado para el algoritmo está dominado por el tiempo para encontrar la primera intersección de esferas, antes de que el problema se simplifique eliminando cualquier punto. Este tiempo es${\displaystyle O(n\log n)}$. ^{[ 5 ]} Ramos proporciona un algoritmo no aleatorio utilizando ε-nets para desaleatorizar una variación del algoritmo de Clarkson y Shor, con el mismo tiempo de ejecución asintótico. ^{[ 6 ]}

En cualquier dimensión fija${\displaystyle d}$, existe un algoritmo para el cual el exponente de${\displaystyle n}$en el límite de tiempo es menor que dos. ^{[ 7 ]} También es posible aproximar el diámetro, con una precisión de un${\displaystyle (1+\varepsilon )}$relación de aproximación , en el tiempo${\displaystyle O(n+\varepsilon ^{1/2-d})}$. ^{[ 8 ]}

• Diámetro cinético (datos) , el problema algorítmico de mantener el diámetro de puntos en movimiento.
• Árbol de expansión de diámetro mínimo , una noción diferente de diámetro para puntos de baja dimensión basada en el diámetro gráfico de un árbol de expansión.