¿Cómo encontrar los dos puntos más distantes utilizando solo la métrica de distancia (en lugar de las coordenadas)?

Me encuentro con una pregunta en la que, dado un conjunto de puntos de datos, necesito encontrar dos puntos que estén más alejados. En mi caso, no hay coordenadas para cada punto, solo puedo calcular la distancia entre dos puntos con una métrica de distancia específica (que cumple con los tres axiomas: identidad de los indiscernibles, simetría y desigualdad triangular).

Sé que si estos puntos están en el plano, es decir, si tienen coordenadas, entonces existen algoritmos mejores que O (n ^ 2) para encontrar los dos puntos más alejados, por ejemplo, esta pregunta https://stackoverflow.com/questions/2736290/how-to-find-two-most-distant-points. Pero, ¿existe algún algoritmo mejor que O (n ^ 2) que pueda resolver mi pregunta?

¡Gracias!