Placer une paire de points une approche différente

Question

J'essayais de résoudre ce problème et j'ai trouvé une solution comme ci-dessous, ce qui est assez différent de l'algorithme "Wikipedia". Je n'arrive pas à comprendre ce qui ne va pas avec ma solution, qui est aussi O (nlogn).

Entrée: jeu de coordonnées le long de l'axe x-y. {(2,4), (5,3), (3,7), (4,2), (6,3)}

Ma solution:

1. Trier ensemble donné wrt x-coordonnées. {(2,4), (3,7), (4,2), (5,3), (6,3)}. Complexité O (nlog)
2. Trouvez la min {distance entre paires consécutives}, appelons-la min_x. Complexité O (n)
3. Trier un ensemble donné par ses coordonnées y. {(4,2), (5,3), (6,3), (2,4), (3,7)}. Complexité O (nlog)
4. Trouvez la min {distance entre paires consécutives}, appelons-la min_y. Complexité O (n)
5. min_d = min (min_x, min_y) la paire qui a abouti à min_d est la paire ayant la distance la plus courte.

Est-ce faux? Qu'est-ce que je rate?

Answer 1

Oui, c'est faux. Considérons l'ensemble {(0, 0), (0, 10), (10, 0), (0,2, 0,2)} comme un contre-exemple. Votre approche n'aura jamais (0,0) et (0,2, 0,2) comme éléments consécutifs dans chaque ordre et ne sera donc jamais trouvée comme les deux points les plus proches les uns des autres.

Answer 2

Votre algorithme donnera une paire optimale défectueuse, par ex. l'exemple suivant:

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)) */