Encontrar el diámetro de un conjunto más rápido que $O(|M|^2)$

Question

$M$ es un conjunto finito de puntos en un espacio métrico. Quiero calcular el diámetro del conjunto, es decir, la mayor distancia entre dos puntos. Es allí una manera más inteligente de hacer esto que para calcular la distancia entre todos los pares de puntos?

$$ \delta = \max_{x,y\in M} d(x,y) $$

Supongo que el triángulo de la desigualdad podría dejarme saber que a cierta distancia no tiene que ser calculado, pero parece como un montón de trabajo para hacer las comprobaciones, y la función de distancia no es muy caro.

En caso de que alguien preguntaba, los puntos son de longitud-latitud puntos y la función de distancia la distancia ortodrómica (que es una métrica).

Answer 1

Creo que esto se puede hacer en $O(n$registro$n)$ donde $n$ es el número de puntos. Los algoritmos que vi a utilizar la distancia Euclídea, pero creo que puede ser sustituida por cualquier métrica de medida de distancia. Yo no soy consciente de que la distancia ortodrómica, pero si es la métrica, a continuación, este método debería funcionar.

La idea es calcular el convex-hull de los puntos, que se puede hacer en $O(n$registro$n)$, y, a continuación, encontrar la pareja de más puntos de los vértices de este convex hull en $O(n)$ del tiempo.

Echar un vistazo a una similar pregunta sobre la distancia Euclídea. Descripción del algoritmo se puede encontrar aquí. Aquí es un papel el tratamiento de diámetro cálculos en $d$ dimensiones.