Алгоритам две најближе тачке

Алгоритам две најближе тачке се користи у разним областима рачунарства. На пример, користи се у попуњавању површина на 3D моделима, за одређивање најкраћег растојања између елемената у електричним колима, детектовање судара два објекта и слично.

Проблем

У равни је дато n тачака својим координатама (х, у). Одредити растојање на којем су две најближе тачке. Овде ћемо се бавити само дводимензионалним проблемом, мада се проблем може проширити и на више димензија.

Једно наивно решење

Наивно решење проблема било би да проверимо растојање између сваке две тачке.

 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]);
     }
   }
 }

Ово решење изискује О(n²) операција. Постоји боље решење.

Оптималније решење^[1]

Ово решење се заснива на принципу подели па владај. Алгоритам је следећи:

Сортирају се тачке по Х координати.
Поделе се тачке на две групе са подједнаким бројем тачака једном вертикалном линијом.
Нађу се рекурзивно најкраћа растојања за леву и десну страну и назову се dLmin i dRmin.
Нека је d = min(dLmin, dRmin). То растојање не мора да буде наше тражено растојање јер постоји могућност да се две најближе тачке налазе баш са различитих страна наше вертикалне линије, али да су јако близу. Зато морамо и то да проверимо.
Направи се појас ширине 2d око наше вертикалне линије и одстране се све тачке које не припадају појасу.
Нађу се растојања између тачака у појасу и нађе се најмање. Ако је оно мање од d, онда је то тражено растојање. У супротном је d најмање растојање.
Постоји једно мало запажање које је корисно напоменути. За сваку тачку у појасу довољно је да се провери само 6 тачака (за разлику од провераве свих тачак у појасу). За велики број тачака, ово може да буде значајан податак. Тиме са квадратног времена прелазимо на линеарно.

Да би се све то урадило, неоходно да су тачке сортиране по y координати.

Сложеност алгоритма

Ако se не користи приступ последњег корака, сложеност је О(n²), јер је неопходно да се у последњем кораку упореде све тачке са сваком у нашем појасу. Међутим, ако се искористи тај приступ, морају се сортирати тачке у појасу (сложеност је О(n logn)), и остварује се линеарни пролаз кроз њих (О(n)), што на крају даје О(n logn) - бољу сложеност.

Имплементација оптималнијег алгоритма у 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;
 }

Референце

^ Closest Pair: A Divide-and-Conquer Approach

Литература

Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. стр. 957—961. ISBN 978-0-262-03293-3. .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

[1] Closest Pair: A Divide-and-Conquer Approach

[1]