Problema unei perechi de puncte cele mai apropiate

Cea mai apropiată problemă de pereche este o problemă de geometrie computațională . Având în vedere n puncte într-un spațiu metric , trebuie să găsiți o pereche de puncte cu cea mai mică distanță între ele.

Problema punctului cel mai apropiat din planul euclidian [1] a fost una dintre primele probleme geometrice care a fost studiată sistematic în ceea ce privește complexitatea de calcul a algoritmilor geometrici .

Un algoritm naiv pentru găsirea distanțelor dintre toate perechile dintr-un spațiu de dimensiunea d și alegerea celei mai mici dintre ele necesită timp O ( n 2 ) . Rezultă că problema poate fi rezolvată în timp în spațiu euclidian sau L p spațiu de dimensiune fixă d [2] . În modelul de calcul algebric al arborelui de decizie , algoritmul cu timpul O( n log n ) este optim atunci când este redus din problema unicității elementului $O(n\log n)$ . Într-un model de calcul care presupune că funcția floor este calculată în timp constant, problema poate fi rezolvată în timp [3] . Dacă permitem aplicarea aleatoriei împreună cu funcția de etaj , problema poate fi rezolvată în timp O( n ) [4] [5] . $O(n\log \log n)$

Algoritm de forță brută

Perechea de puncte cele mai apropiate poate fi calculată în timp O ( n2 ) prin efectuarea unei enumerari complete . Pentru a face acest lucru, puteți calcula distanța dintre toate n ( n − 1) / 2 perechi de puncte, apoi alegeți perechea cu distanța cea mai mică, așa cum se arată mai jos.

minDist = infinit pentru i = 1 la lungime ( P ) - 1 pentru j = i + 1 la lungime ( P ) fie p = P [ i ], q = P [ j ] dacă dist ( p , q ) < minDist : minDist = dist ( p , q ) closestPair = ( p , q ) return closestPair

Caz planar

Problema poate fi rezolvată în timp folosind o abordare recursivă împărțire și cuceri , ca aceasta [1] : $O(n\log n)$

Sortați punctele în funcție de coordonatele lor x;
Împărțim mulțimea de puncte în două submulțimi de dimensiuni egale ale dreptei verticale ; $x=x_{mid)$
Rezolvăm problema recursiv pe partea stângă și dreapta. Aceasta are ca rezultat o distanță minimă la stânga și, respectiv, o distanță minimă la dreapta ; $d_{Lmin}$ $d_{Rmin}$
Găsim distanța minimă între perechi de puncte, dintre care un punct se află la stânga dreptei verticale, iar celălalt punct se află la dreapta dreptei; $d_{LRmin)$
Răspunsul final va fi valoarea minimă dintre , și . $d_{Lmin}$ $d_{Rmin}$ $d_{LRmin)$

Se pare că pasul 4 poate fi finalizat în timp liniar. Din nou, abordarea naivă ar necesita calcularea distanțelor pentru toate perechile stânga/dreapta, adică timp pătratic. Observația cheie se bazează pe următoarea proprietate de sparsitate a mulțimii de puncte. Știm deja că cea mai apropiată pereche de puncte nu sunt mai îndepărtate decât . Prin urmare, pentru fiecare punct p din stânga dreptei de despărțire, trebuie să comparăm distanțele față de punctele care se află într-un dreptunghi cu dimensiuni (dist, 2 ⋅ dist) așa cum se arată în figură. Și acest dreptunghi nu poate conține mai mult de șase puncte, distanța pe perechi dintre care nu este mai mică de . Astfel, este suficient să calculăm 6 n distanțe la pasul 4 [6] . Relația de recurență pentru numărul de pași poate fi scrisă ca , care poate fi rezolvată folosind teorema fundamentală pentru împărțirea și cucerirea recurenței , care dă . $\mathrm {dist} =\min(d_{Lmin},d_{Rmin})$ $d_{Rmin}$ $T(n)=2T({\tfrac {n}{2)))+O(n)$ $O(n\log n)$

Deoarece o pereche de puncte cele mai apropiate definește o muchie într-o triangulație Delaunay și corespund la două celule adiacente într- o diagramă Voronoi , o pereche de puncte cele mai apropiate poate fi determinată în timp liniar dacă este dată una dintre cele două structuri. Calcularea unei triangulații Delaunay sau a unei diagrame Voronoi necesită timp . Aceste abordări nu sunt eficiente pentru dimensiunile d >2 , în timp ce algoritmul de împărțire și cucerire poate fi generalizat la timpul de execuție pentru orice valoare constantă a dimensiunii d . $O(n\log n)$ $O(n\log n)$

Problemă dinamică cea mai apropiată pereche

Versiunea dinamică pentru problema unei perechi de puncte cele mai apropiate este stabilită după cum urmează:

Având în vedere un set dinamic de obiecte, găsiți algoritmi și structuri de date pentru a recalcula eficient o pereche de puncte cele mai apropiate de fiecare dată când un obiect este inserat sau îndepărtat.

Dacă caseta de delimitare pentru toate punctele este cunoscută dinainte și este disponibilă o funcție de etaj cu timp de rulare constant, atunci a fost propusă o structură de date cu o memorie așteptată de O( n ) care acceptă un timp așteptat (timp mediu) de inserare și ștergere. de O(log n ) și un timp constant de interogare. Dacă problema este modificată pentru un model de arbore de decizie algebric, inserările și ștergerile vor necesita un timp mediu [7] . Trebuie remarcat faptul că complexitatea problemei dinamice de mai sus a unei perechi de puncte cele mai apropiate depinde exponențial de dimensiunea d , astfel încât algoritmul devine mai puțin potrivit pentru problemele de dimensiuni mari. $O(\log ^{2}n)$

Un algoritm pentru problema dinamică a unei perechi de puncte cele mai apropiate dintr-un spațiu de dimensiunea d a fost dezvoltat de Sergey Bespamyatnykh în 1998 [8] . Punctele pot fi inserate și îndepărtate în O(log n ) timp per punct (cel mai rău caz).

Vezi și

Note

↑ 1 2 Shamos, Hoey, 1975 , p. 151-162.
↑ Clarkson, 1983 .
↑ Fortune, Hopcroft, 1979 , p. 20-23.
↑ Khuller și Matias 1995 , p. 34-37.
↑ Richard Lipton. Rabin aruncă o monedă (24 septembrie 2011). Consultat la 19 februarie 2019. Arhivat din original pe 16 februarie 2019. (nedefinit)
↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 957-961 33.4: Găsirea celei mai apropiate perechi de puncte..
↑ Golin, Raman, Schwarz, Smid, 1998 .
↑ Bespamyatnikh, 1998 , p. 175-195.

Literatură

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Introducere în algoritmi. - A doua editie. - MIT Press și McGraw-Hill, 2001. - ISBN 0-262-03293-7 .
- Traducere: Thomas Cormen, Charles Leizerson, Ronald Rivest, Clifford Stein. Algoritmi: construcție și analiză . - a doua editie. - Moscova, Sankt Petersburg, Kiev: „Williams”, 2005. - ISBN 5-8459-0857-4 BBC 32.973.26-018.2.75.
Jon Kleinberg, Eva Tardos. Proiectarea algoritmului . - Addison Wesley, 2006.
- Traducere: John Kleinberg , Eva Tardos . Algoritmi. Dezvoltare și aplicare. - Moscova, Sankt Petersburg, Nijni Novgorod, Kiev: Peter, 2016. - (Classics of Computer Science). - ISBN 978-5-496-01545-5 BBC 32.973.2-018.
Michael Ian Shamos, Dan Hoey. Probleme la cel mai apropiat punct // Proc. Al 16-lea simpozion anual IEEE privind fundamentele informaticii (FOCS). - 1975. - doi : 10.1109/SFCS.1975.8 .
Fortune S., Hopcroft JE O notă despre algoritmul celui mai apropiat vecin al lui Rabin // Scrisori de procesare a informațiilor. - 1979. - T. 8 , nr. 1 .
Clarkson KL Cel de-al 24-lea simpozion anual privind fundamentele informaticii. — 1983.
Khuller S., Matias Y. A simple randomized sieve algorithm for the closest-pair problem // Inf. Calculator. - 1995. - T. 118 , nr. 1 .
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid. Structuri de date randomizate pentru problema dinamică a celei mai apropiate perechi // SIAM J. Comput. . - 1998. - T. 26 , nr. 4 . Versiunea preliminară a fost prezentată la simpozionul „4th Annu. ACM-SIAM Symp. despre algoritmi discreti”, 1993, p. 301-310
Serghei N. Bespamyatnikh. Un algoritm optim pentru întreținerea celei mai apropiate perechi // Calculator discret. Geom. - 1998. - Emisiune. 19 .
Note de curs UCSB
rosettacode.org — Cea mai apropiată pereche de puncte implementate în mai multe limbaje de programare
Algoritm de baleiaj de linie pentru cea mai apropiată problemă de pereche