TD4 - Distance entre des points

(* Exercice 1

1. Algorithme naïf : on va regarder la distance entre chaque point.
La distance entre deux points [x,y] et [a,b] est :
sqrt( (x-a)² + (y-b)² )
Si on veut juste comparer des distances, autant ne pas appliquer la racine carrée, étant bijective sur les positifs.

Donc on crée une première fonction qui regarde la distance entre 1 point donné et tous les autres, et une seconde fonction qui va appliquer celle-ci en tout point.

2. *)

let algo_naif l =
    let rec aux1 l x_fixe y_fixe best_distance = match l with
    |[] -> best_distance
    |(x,y)::t when ( (x-.x_fixe)**2. +. (y-.y_fixe)**2. ) < best_distance -> aux1 t x_fixe y_fixe ((x-.x_fixe)**2. +. (y-.y_fixe)**2.)
    |(x,y)::t -> aux1 t x_fixe y_fixe best_distance
    in

    let rec aux2 l best_distance = match l with
    |[] -> best_distance
    |(x,y)::t -> let bd = (aux1 t x y best_distance) in aux2 t bd
    in
match l with
|[] -> -1.
|(x,y)::[] -> -1.
|(x,y)::(a,b)::t -> let premiere_distance = ( (x-.a)**2. +. (y-.b)**2. ) in sqrt(aux2 l premiere_distance);;

(* Exercice 2 :
Dans le cas où il n'y a qu'une seule coordonnée, on pourrait simplement trier la liste des coordonnées par un tri par fusion (en n*lg(n)), et vérifier la distance entre 2 éléments consécutifs (n comparaisons).
La complexité est en n + n*lg(n) soit O(n*lg(n)) *)


(* Exercice 3 :

1ère étape : trier par ordre lexicographique. Trier les abscisses prend n*lg(n), et trier les ordonnées après donne 2*n*lg(n) (soit O(n lg(n)))

2ème étape : on coupe à la moitié, et on applique notre fonction de l'exo 2 aux deux sous-listes O(n * lg(n)) + O(1)
On obtient d1,d2 donc delta = min(d1,d2)

3ème étape : le meilleur des cas est en O(1), le pire est en O(n²)

Total meilleur des cas:
c(n) = O(n*lg(n)) + O(n*lg(n)) + O(1) = O(n*lg(n))

Total pire des cas :
c(n) = O(n*lg(n)) + O(n*lg(n)) + O(n²) = O(n²) *)