Closet пара точек другой подход

Question

Я пытался решить эту проблему, и я придумал решение, как показано ниже, что сильно отличается от алгоритма «Википедия». Я не понимаю, что не так с моим решением, которое также является O (nlogn).

Ввод: Набор координат по оси x-y. {(2,4), (5,3), (3,7), (4,2), (6,3)}

Мой Решение:

1. Сортировка данного множества WRT х-координаты. {(2,4), (3,7), (4,2), (5,3), (6,3)}. Сложность O (nlog)
2. Найдите минимальное расстояние между последовательной парой, давайте назовем его min_x. Сложность O (n)
3. Сортировка заданного набора по y-координатам. {(4,2), (5,3), (6,3), (2,4), (3,7)}. Сложность O (nlog)
4. Найдите минимальное расстояние между последовательной парой, давайте назовем его min_y. Сложность O (n)
5. min_d = min (min_x, min_y) пара, в результате которой min_d является парой с самым коротким расстоянием.

Неправильно? Что мне не хватает?

Answer 1

Да, это неправильно. Рассмотрим встречный пример {(0, 0), (0, 10), (10, 0), (0.2, 0.2)}. Ваш подход никогда не будет иметь (0,0) и (0,2, 0,2) в качестве последовательных элементов в любом порядке и, следовательно, никогда не будет считаться двумя ближайшими друг к другу точками.

Answer 2

Вы алгоритм даст дефектную оптимальную пару, например. в следующем примере:

var points : [(Int,Int)] = [(0,0),(1,10),(10,1),(3,3)] 

/* xmin solution: (1,10), (3,3) (dist = sqrt(4+49) = sqrt(53)) 
    from sorted list: (0,0),(1,10),(3,3),(10,1)     */ 

/* ymin solution: (10,1), (3,3) (dist = sqrt(53)) 
    from sorted list: (0,0),(10,1),(3,3),(1,10)     */ 

/* real solution: (0,0), (3,3) (dist = sqrt(18) < sqrt(53)) */