Алгоритм для синтеза набора двумерных точек

Question

У меня есть набор двумерных точек/координат, и мне нужно, чтобы между всеми парами точек было соблюдено определенное минимальное расстояние. Кроме того, каждая точка связана с некоторой информацией, которую я хотел бы поддерживать, возможно, слияние этой информации с другой информацией, содержащейся в других точках.

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

Я не могу придумать алгоритм или метод, который решает эту проблему в любой временной стоимости.

Любая помощь будет оценена по достоинству.

Answer 1

Наивное решение - не быстро (O (n³)), но, возможно, вы начали:

1. Найти минимальное расстояние между любыми двумя точками, то есть пары точек, которые во всем мире имеют минимальное расстояние (O (n²))
2. Если расстояние больше необходимого минимума, вы сделали
3. Объединить две точки и начать на 1.

это объединяет пункты, которые наиболее близко друг к другу один от на e используйте алгоритм грубой силы до тех пор, пока не будет достигнуто минимальное расстояние.

P.S .: Как отмечает @Yyes Dauous в комментариях, закрывающая пара может быть найдена в O (n log n), как описано, например, в соответствующей статье Википедии (которая включает в себя некоторое обсуждение динамических аспектов, которые могут быть здесь полезны): https://en.wikipedia.org/wiki/Closest_pair_of_points_problem