Algoritam dve najbliže tačke

Najbliži par tačaka je prikazan crvenom bojom

Algoritam dve najbliže tačke se koristi u raznim oblastima računarstva. Na primer, koristi se u popunjavanju površina na 3D modelima, za određivanje najkraćeg rastojanja između elemenata u električnim kolima, detektovanje sudara dva objekta i slično.

Problem

U ravni je dato n tačaka svojim koordinatama (h, u). Odrediti rastojanje na kojem su dve najbliže tačke. Ovde ćemo se baviti samo dvodimenzionalnim problemom, mada se problem može proširiti i na više dimenzija.

Jedno naivno rešenje

Naivno rešenje problema bilo bi da proverimo rastojanje između svake dve tačke.

 min = distance(points[0],points[1]);
 for ( i = 0; i < n; i++)
 {
   for ( j = i+1; j < n; j++)
   {
     if (distance(points[i],points[j]) < min)
     {
       min = distance(points[i],points[j]);
     }
   }
 }

Ovo rešenje iziskuje O(n²) operacija. Postoji bolje rešenje.

Optimalnije rešenje

Ovo rešenje se zasniva na principu podeli pa vladaj. Algoritam je sledeći:

1. Sortiraju se tačke po H koordinati.
2. Podele se tačke na dve grupe sa podjednakim brojem tačaka jednom vertikalnom linijom.
3. Nađu se rekurzivno najkraća rastojanja za levu i desnu stranu i nazovu se dLmin i dRmin.
4. Neka je d = min(dLmin, dRmin). To rastojanje ne mora da bude naše traženo rastojanje jer postoji mogućnost da se dve najbliže tačke nalaze baš sa različitih strana naše vertikalne linije, ali da su jako blizu. Zato moramo i to da proverimo.
5. Napravi se pojas širine 2d oko naše vertikalne linije i odstrane se sve tačke koje ne pripadaju pojasu.
6. Nađu se rastojanja između tačaka u pojasu i nađe se najmanje. Ako je ono manje od d, onda je to traženo rastojanje. U suprotnom je d najmanje rastojanje.
7. Postoji jedno malo zapažanje koje je korisno napomenuti. Za svaku tačku u pojasu dovoljno je da se proveri samo 6 tačaka (za razliku od proverave svih tačak u pojasu). Za veliki broj tačaka, ovo može da bude značajan podatak. Time sa kvadratnog vremena prelazimo na linearno.

Da bi se sve to uradilo, neohodno da su tačke sortirane po y koordinati.

Složenost algoritma

Ako se ne koristi pristup poslednjeg koraka, složenost je O(n²), jer je neophodno da se u poslednjem koraku uporede sve tačke sa svakom u našem pojasu. Međutim, ako se iskoristi taj pristup, moraju se sortirati tačke u pojasu (složenost je O(n logn)), i ostvaruje se linearni prolaz kroz njih (O(n)), što na kraju daje O(n logn) - bolju složenost.

Implementacija optimalnijeg algoritma u C++

 #include <iostream>
 #include <vector>
 #include <algorithm>

 using namespace std;

 #define BESKONACNOST 1E10
 #define EPSILON 1E-10
 #define MAX_VELICINA 1000

 // definisemo strukturu Tacka
 struct Tacka	
 {
 double _x;
 double _y;
 Tacka () { _x = BESKONACNOST; _y = BESKONACNOST; }
 Tacka ( double x, double y ) { _x = x; _y = y; }
 };
 
 // globalne promenljive
 int n;
 vector<Tacka> tacke(MAX_VELICINA);

 bool sortirajPoX(const Tacka& A, const Tacka& B)
 {
   //if (A._x == B._x) return A._y < B._y;
   return A._x < B._x;
 }
 bool sortirajPoY(int i, int j)
 {
   //if (tacke[i]._y == tacke[j]._y) return tacke[i]._x < tacke[j]._x;
   return tacke[i]._y < tacke[j]._y;
 }
 // ovo vraca kvadrat rastojanja
 double rastojanjeTacaka(const Tacka& A, const Tacka& B)
 { 
   return (A._x - B._x) * (A._x - B._x) + (A._y - B._y) * (A._y - B._y);
 }
 double resi(int indeksiTacakaSortiranihPoY[MAX_VELICINA], int levi, int desni)
 {
   int i,j,k;
   double dLmin,dDmin,dmin;
   int N = desni - levi;
   int s = (levi + desni)/2;
   if (N <= 1) return BESKONACNOST;
   if (N == 2) return rastojanjeTacaka(tacke[indeksiTacakaSortiranihPoY[0]], tacke[indeksiTacakaSortiranihPoY[1]]);
   // podeli niz na dva dela
   int b[MAX_VELICINA];
   i=0;
   j= s - levi;
   for ( k = 0; k < N; k++)
   {
      if (indeksiTacakaSortiranihPoY[k] <= s && i < s-levi)
         b[i++] = indeksiTacakaSortiranihPoY[k];
      else
         b[j++] = indeksiTacakaSortiranihPoY[k];		
   }
   // nadji minimume u levoj i desnoj polovini rekurzivno	
   dLmin = resi(b,levi, s);
   dDmin = resi(b,s+1, desni);
   dmin = min(dLmin, dDmin);
   // pronadji ako ima bolje resenje
   int indeksiTacakaUPojasu[MAX_VELICINA];
   int t = 0;
   // izdvoj samo tacke u pojasu [-dmin,dmin] oko vertikalne linije koja razdvaja
   for ( k = 0; k < N; k++)
   {
      if (fabs(tacke[indeksiTacakaSortiranihPoY[k]]._x - tacke[s]._x) - dmin < EPSILON)
      {
         indeksiTacakaUPojasu[t++] = indeksiTacakaSortiranihPoY[k];
      }
   }
   // nadji rastojanja izmedju tacaka u pojasu i pronadji najmanje 
   for (int i=0; i<t-1; i++)
   {
      for (j= min(i+7,t-1); j>i; j--)
      {
         double rastojanje = rastojanjeTacaka(tacke[indeksiTacakaUPojasu[i]], tacke[indeksiTacakaUPojasu[j]]);
         if (rastojanje < dmin)
         {
            dmin = rastojanje;
         }
       }
   }
   return dmin;
 }
 double najkraceRastojanje()
 {
   int indeksiTacakaSortiranihPoY[MAX_VELICINA];
   for (int i = 0 ; i < n ; i++ ) indeksiTacakaSortiranihPoY[i] = i;
   sort(tacke.begin(),tacke.begin()+n,sortirajPoX);
   sort(indeksiTacakaSortiranihPoY, indeksiTacakaSortiranihPoY + n, sortirajPoY);
   return resi(indeksiTacakaSortiranihPoY, 0, n);
 }
 int main()
 {
   double resenje;
   // ucitamo broj tacaka
   cin >> n;
   // ucitavanje tacaka
   for (int i=0;i<n;i++)
   {
     cin >> tacke[i]._x;
     cin >> tacke[i]._y;
   }
   // nadjemo resenje
   resenje = sqrt(najkraceRastojanje());
   cout << resenje << endl;
   return 0;
 }

Literatura

• Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms (2nd izd.). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. CS1 održavanje: Višestruka imena: spisak autora (veza). Pages 957-961 of section 33.4: Finding the closest pair of points.
• Jon Kleinberg; Tardos, Éva (2006). Algorithm Design. Addison Wesley. 
• UCSB Lecture Notes
• rosettacode.org - Closest pair of points implemented in multiple programming languages
• Line sweep algorithm for the closest pair problem