Следующая проблема ближайшей пары

Question

Я уверен, что большинство знакомо с проблемой ближайшей пары , но есть ли другой алгоритм или способ изменить текущий алгоритм CP для получения следующей ближайшей пары?1005 *

Answer 1

Легко, O (n log (n)):

• найти пару шкафов (p1, p2) в O (n log (n))
• вычисляет все пары с p1 или p2 (но не (p1, p2)), оставляя ближайшую, назовем ее E в O (n)
• удалить p1 и p2 в (1)
• найдите пару шкафов, сравните ее с E и сохраните ближайшую, снова в O (n log (n))

Теперь у вас есть второй ближайший.

Answer 2

Если необходимо постоянное количество минимальных расстояний ( следующие пары), можно изменить шаги 3-5 из статьи в Википедии, переопределив d_Lmin, d_Rmin, d_LRmin в качестве списков минимальных расстояний постоянной длины.При этом используется память c * log (n).

Если next используется менее чем за O (n) раз, чем переформулировка задачи CR для возврата на меньшее расстояние, большее, чем заданное d соответствует методу next .Это может быть реализовано с тем же подходом, что и CR.Я не вижу теоретической гарантии, что шаг 4 может быть выполнен за линейное время, но есть преимущество, чтобы не отмечать точки в маленьких прямоугольниках.

Если next используется больше, чем O (n) раз, чем лучше рассчитать все расстояния и отсортировать их (если память не проблема).