Probleme – La paire de points la plus proche, du croquis au programme

1. Le programme.

(* Distance minimale entre deux points de p. Précondition : au moins 2 points.
   Complexité : Theta(n log^2 n) telle qu'écrite, Theta(n log n) si l'on
   maintient aussi le tri par ordonnée à la remontée. *)
let plus_proche p0 =
  let n = Array.length p0 in
  let px = Array.copy p0 in
  Array.sort (fun (x1,_) (x2,_) -> compare x1 x2) px;      (* tri par ABSCISSE *)
  let carre (x1,y1) (x2,y2) = (x1-.x2)*.(x1-.x2) +. (y1-.y2)*.(y1-.y2) in
  let rec resoudre g d =                                   (* px.[g .. d-1] *)
    if d - g <= 3 then begin                               (* cas de base : brute *)
      let m = ref infinity in
      for i = g to d-2 do for j = i+1 to d-1 do
        let e = carre px.(i) px.(j) in if e < !m then m := e done done;
      !m
    end else begin
      let mi = g + (d - g) / 2 in
      let (xm, _) = px.(mi) in
      let delta = min (resoudre g mi) (resoudre mi d) in
      (* la BANDE : les points à moins de delta de la coupure, triés par ORDONNÉE *)
      let bande = Array.of_list (List.filter (fun (x,_) ->
        (x -. xm) *. (x -. xm) < delta) (Array.to_list (Array.sub px g (d-g)))) in
      Array.sort (fun (_,y1) (_,y2) -> compare y1 y2) bande;
      let m = ref delta and nb = Array.length bande in
      for i = 0 to nb - 1 do
        let j = ref (i+1) in
        (* on s'arrête dès que l'écart d'ORDONNÉE dépasse la distance courante *)
        while !j < nb && (let (_,yj) = bande.(!j) and (_,yi) = bande.(i) in
                          (yj -. yi)*.(yj -. yi) < !m) do
          let e = carre bande.(i) bande.(!j) in
          if e < !m then m := e;
          incr j
        done
      done;
      !m
    end
  in sqrt (resoudre 0 n)          (* UNE seule racine carrée, tout à la fin *)

On travaille sur les distances au carré, et l'on ne prend la racine qu'à la toute dernière ligne : cela évite $\Theta (n\log n)$ racines carrées, et surtout les erreurs d'arrondi du chapitre chap:algo-prog — la comparaison de deux carrés est exacte sur des flottants là où celle de deux racines ne l'est pas toujours.

C'est aussi l'endroit où l'on se trompe. La fonction interne resoudre rend un carré, la fonction externe une distance : oublier le sqrt final donne un programme qui compile, qui ne plante jamais, et qui rend $0,0341$ au lieu de $0,1848$. Le défaut a été trouvé en confrontant le résultat à la force brute sur des instances à deux points — le plus petit cas possible. Quand deux quantités de même type portent des unités différentes, la frontière entre elles doit être écrite dans la spécification, et éprouvée sur le cas trivial.

2. La borne, et sa démonstration. Soit $\delta$ le minimum des deux moitiés, et deux points $u,v$ de la bande avec $y_v-y_u\ge \delta$. Alors leur distance vaut au moins $\delta$ : inutile de les comparer. Il suffit donc, pour chaque point de la bande, de regarder les suivants tant que leur ordonnée reste à moins de $\delta$.

Combien peut-il y en avoir ? Considérons le rectangle de largeur $2\delta$ (la bande) et de hauteur $\delta$ au-dessus de $u$. Il se découpe en huit carrés de côté $\delta /2$. Chaque carré contient au plus un point : deux points d'un même carré seraient à distance au plus $\frac{\delta }{2}\sqrt{2}<\delta$, or ils seraient tous deux du même côté de la coupure — les carrés ne chevauchent pas la médiane — ce qui contredirait la définition de $\delta$. Le rectangle contient donc au plus $8$ points, dont $u$ : au plus $7$ voisins à examiner, une constante.

C'est ce qui rend la combinaison linéaire, et donne $T(n)=2T(n/2)+\Theta (n\log n)=\Theta (n{\log }^{2}n)$ telle qu'écrite — le $\log$ supplémentaire venant du tri de la bande. En remontant les listes triées par ordonnée comme dans une fusion, on supprime ce tri et l'on atteint $\Theta (n\log n)$.

3. La mesure. Les deux méthodes ont rendu exactement la même distance sur toutes les instances.

La dernière colonne est le nombre maximal de voisins effectivement examinés dans la bande, tous appels confondus : jamais plus de $2$, alors que la borne démontrée est $7$. C'est normal, et instructif : la borne est un pire cas géométrique, atteint seulement par des configurations très particulières. Une borne de complexité n'est pas une prédiction de mesure.

4. Sans le tri par ordonnée. La boucle intérieure s'arrête sur le premier point dont l'ordonnée s'écarte de plus de $\delta$. Si la bande n'est pas triée, ce test n'a plus aucun sens : il coupe la recherche au premier point éloigné venu, alors que le plus proche pouvait être juste après. L'algorithme rend alors une distance trop grande, silencieusement — et il la rend vite, ce qui est le pire des cas de figure.

Si l'on supprime le test d'arrêt en plus du tri, on retrouve la correction et la complexité quadratique : la bande peut contenir les $n$ points. Le tri n'est donc pas une optimisation : c'est ce qui rend le critère d'arrêt licite. C'est le même constat qu'à l'exercice 14.5 — trier achète le droit de s'arrêter tôt.