Я с этим методом "разделяй и властвуй" уже сталкивался – разбить точки на части, рекурсия, потом объединить полосу. Для реальных данных я бы сначала отсортировал по X, а потом для каждого рекурсивного вызова держал бы отдельный список, отсортированный по Y, чтобы не пересортировывать постоянно. Если данных немного, то простая сетка даст вполне приличный результат и можно будет без рекурсии обойтись. Главное – найти баланс между дополнительной памятью, предобработкой и реальной скоростью, которую ты получишь для конкретного распределения. Хорошая практика, чтобы увидеть, где теория встречается с грязными деталями реальной системы.

Звучит убедительно. Но я бы всё равно обратил внимание на несколько нюансов: если много точек имеют одинаковую координату по X или Y, то поиски могут дать сбой, поэтому небольшой запас помогает. Дубликаты точек приводят к нулевому минимальному расстоянию, поэтому стоит сразу прерывать вычисления, если обнаружишь повтор. А ещё, не забывай про погрешность вычислений с плавающей точкой — используй целочисленные координаты или надёжную функцию сравнения, чтобы результат был стабильным. И, напоследок, если данные охватывают огромный диапазон, нормализация координат перед разбиением на ячейки поможет сохранить разумный размер сетки. Это обычно самые коварные подводные камни на практике.

Обычно я выбираю очень маленькое эпсилон, исходя из масштаба данных – например, 1e-9 от максимального значения координаты. Затем каждое сравнение расстояний сводится к “если расстояние меньше эпсилон, считаем его нулём”. Это простой способ защититься от ошибок округления, и я оборачиваю все вычисления в отдельную функцию, чтобы не забывать об этом каждый раз. Если числа очень большие или нужна высокая точность, перехожу на относительную погрешность или даже использую библиотеку для работы с десятичными числами в самых критичных местах. Так код остаётся читабельным, при этом не теряется точность.