Python: ускорение географического сравнения

Я написал код, который включает вложенный цикл, в котором внутренний цикл выполняется примерно 1,5 миллиона раз. У меня есть функция в этом цикле, которую я пытаюсь оптимизировать. Я проделал некоторую работу и получил некоторые результаты, но мне нужен небольшой вклад, чтобы проверить, разумно ли то, что я делаю.

Немного предыстории:

У меня есть две коллекции географических точек (широта, долгота) , одна относительно небольшая коллекция и одна относительно большая коллекция. Для каждой точки в маленькой коллекции мне нужно найти ближайшую точку в большой коллекции.

Очевидный способ сделать это - использовать формулу гаверсинуса. Преимущество здесь в том, что расстояния определенно точны.

from math import radians, sin, cos, asin, sqrt

def haversine(point1, point2):
    """Gives the distance between two points on earth.
    """
    earth_radius_miles = 3956
    lat1, lon1 = (radians(coord) for coord in point1)
    lat2, lon2 = (radians(coord) for coord in point2)
    dlat, dlon = (lat2 - lat1, lon2 - lon1)
    a = sin(dlat/2.0)**2 + cos(lat1) * cos(lat2) * sin(dlon/2.0)**2
    great_circle_distance = 2 * asin(min(1,sqrt(a)))
    d = earth_radius_miles * great_circle_distance
    return d

Однако выполнение 1,5 миллиона раз на моей машине занимает около 9 секунд (по данным timeit). Поскольку точное расстояние неважно, мне нужно только найти ближайшую точку, я решил попробовать другие функции.

Простая реализация теоремы Пифагора дает мне ускорение примерно на 30%. Думая, что у меня получится лучше, я написал следующее:

def dumb(point1, point2):
    lat1, lon1 = point1
    lat2, lon2 = point2
    d = abs((lat2 - lat1) + (lon2 - lon1))

, что дает мне улучшение в 10 раз. Однако теперь я беспокоюсь, что это не сохранит неравенство треугольника.

Итак, мой последний вопрос состоит из двух вопросов: я бы хотел иметь функцию, которая работает так же быстро, как тупой , но все же быть правильным. Будет ли работать тупой ? Если нет, какие-нибудь предложения о том, как улучшить мою хаверсинусную функцию?