A legközelebbi pont pár problémája

A legközelebbi pár probléma egy számítási geometriai probléma . Adott n pont egy metrikus térben , meg kell találnia egy olyan pontpárt , amelyek között a legkisebb távolság van.

Az euklideszi sík legközelebbi pontproblémája [1] volt az egyik első olyan geometriai probléma, amelyet szisztematikusan tanulmányoztak a geometriai algoritmusok számítási összetettsége szempontjából .

Egy naiv algoritmus a d dimenziójú tér összes párja közötti távolság megtalálására és a legkisebbik kiválasztására O ( n 2 ) időbe telik . Kiderül, hogy a probléma időben megoldható euklideszi térben vagy d rögzített méretű L p térben [2] . Az algebrai döntési fa számítási modellben az O( n log n ) idejű algoritmus optimális, ha csökkentjük az elem egyediségi problémájából $O(n\log n)$ . Egy olyan számítási modellben, amely feltételezi, hogy a padló függvény kiszámítása állandó időben történik, a probléma időben megoldható [3] . Ha megengedjük a véletlenszerűsítés alkalmazását a padlófüggvénnyel együtt , a probléma O( n ) [4] [5] idő alatt megoldható . $O(n\log \log n)$

Brute force algoritmus

A legközelebbi pont párja kiszámítható O ( n2 ) időben egy teljes felsorolással . Ehhez kiszámolhatja az összes n ( n − 1) / 2 pontpár közötti távolságot, majd az alábbiak szerint kiválaszthatja a legkisebb távolságú párt.

minDist = végtelen , ha i = 1 a hosszhoz( P ) - 1 ha j = i + 1 a hosszúsághoz( P ) legyen p = P [ i ], q = P [ j ] , ha dist ( p , q ) < minDist : minDist = dist ( p , q ) closestPair = ( p , q ) return closestPair

Planar case

A probléma időben megoldható egy rekurzív oszd meg és uralkodj megközelítéssel , például [1] : $O(n\log n)$

Rendezd a pontokat x-koordinátáik szerint;
A ponthalmazt felosztjuk a függőleges egyenes két egyenlő nagyságú részhalmazára ; ${\displaystyle x=x_{mid))$
A feladatot rekurzívan oldjuk meg a bal és a jobb oldalon. Ez egy bal oldali minimális távolságot és egy jobb oldali minimális távolságot eredményez; $d_{Lmin}$ $d_{Rmin}$
Megtaláljuk a minimális távolságot a pontpárok között, amelyek közül az egyik pont a függőleges vonaltól balra, a másik pont az egyenestől jobbra található; ${\displaystyle d_{LRmin))$
A végső válasz a minimális érték lesz a , és között . $d_{Lmin}$ $d_{Rmin}$ ${\displaystyle d_{LRmin))$

Kiderült, hogy a 4. lépést lineáris idő alatt lehet végrehajtani. A naiv megközelítés ismételten megkövetelné a távolságok kiszámítását az összes bal/jobb párhoz, azaz négyzetes időt. A kulcsfontosságú megfigyelés a ponthalmaz alábbi ritkasági tulajdonságán alapul. Azt már tudjuk, hogy a legközelebbi pontpárok nincsenek távolabb egymástól, mint . Ezért minden , az osztóvonaltól balra lévő p pontban össze kell hasonlítanunk a távolságokat azokkal a pontokkal, amelyek egy (dist, 2 ⋅ dist) méretű téglalapban helyezkednek el , az ábrán látható módon. És ez a téglalap legfeljebb hat pontot tartalmazhat, amelyek páronkénti távolsága nem kisebb, mint . Így a 4. lépésnél elegendő 6 n távolságot kiszámítani [6] . A lépések számának ismétlődési relációja így írható fel , ami az oszd meg és uralkodj ismétlődés alaptételével oldható meg , ami a következőt adja . $\mathrm {dist} =\min(d_{Lmin},d_{Rmin})$ $d_{Rmin}$ $T(n)=2T({\tfrac {n}{2)))+O(n)$ $O(n\log n)$

Mivel egy Delaunay-háromszögelésben a legközelebbi pont párja határoz meg egy élt, és egy Voronoi-diagram két szomszédos cellájának felel meg , a legközelebbi pontok párja meghatározható lineáris időben, ha a két struktúra közül az egyik adott. Egy Delaunay-háromszögelés vagy egy Voronoi-diagram kiszámítása időt vesz igénybe . Ezek a megközelítések nem hatékonyak d >2 dimenziók esetén, míg az oszd meg és uralkodj algoritmus futásidejűre általánosítható a d dimenzió bármely állandó értékére . $O(n\log n)$ $O(n\log n)$

Dinamikus legközelebbi pár probléma

A legközelebbi pontpár problémájának dinamikus változata

Ha adott egy dinamikus objektumkészlet, keressen algoritmusokat és adatstruktúrákat a legközelebbi pontok párjának hatékony újraszámítására minden egyes objektum beillesztésekor vagy eltávolításakor.

Ha minden pontra előre ismert a határolókeret , és rendelkezésre áll egy állandó futási idejű padlófüggvény, akkor egy O( n ) várt memóriájú adatstruktúrát javasoltak, amely támogatja a beillesztés és törlés várható idejét (átlagos idejét). az O(log n ) és egy állandó lekérdezési idő . Ha a problémát egy algebrai döntési fa modellhez módosítják, a beszúrások és törlések átlagos időt igényelnek [7] . Meg kell jegyezni, hogy a fenti dinamikus probléma összetettsége egy legközelebbi pontpárra exponenciálisan függ a d dimenziótól , így az algoritmus kevésbé alkalmas nagydimenziós feladatokra. $O(\log ^{2}n)$

Szergej Bespamyatnykh 1998-ban dolgozott ki algoritmust egy d dimenziójú térben lévő legközelebbi pontpár dinamikus problémájára [8] . A pontokat O(log n ) idő alatt lehet beilleszteni és eltávolítani pontonként (legrosszabb eset).

Lásd még

Jegyzetek

↑ 1 2 Shamos, Hoey, 1975 , p. 151-162.
↑ Clarkson, 1983 .
↑ Fortune, Hopcroft, 1979 , p. 20-23.
↑ Khuller és Matias 1995 , p. 34-37.
↑ Richard Lipton. Rabin feldob egy érmét (2011. szeptember 24.). Letöltve: 2019. február 19. Az eredetiből archiválva : 2019. február 16. (határozatlan)
↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 957-961 33.4: A legközelebbi pontpár megkeresése.
↑ Golin, Raman, Schwarz, Smid, 1998 .
↑ Bespamyatnikh, 1998 , p. 175-195.

Irodalom

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Bevezetés az algoritmusokba. - Második kiadás. - MIT Press és McGraw-Hill, 2001. - ISBN 0-262-03293-7 .
- Fordítás: Thomas Cormen, Charles Leizerson, Ronald Rivest, Clifford Stein. Algoritmusok: szerkesztés és elemzés . - második kiadás. - Moszkva, Szentpétervár, Kijev: "Williams", 2005. - ISBN 5-8459-0857-4 BBC 32.973.26-018.2.75.
Jon Kleinberg, Tardos Éva. Algoritmus tervezés . - Addison Wesley, 2006.
- Fordítás: John Kleinberg , Eva Tardos . Algoritmusok. Fejlesztés és alkalmazás. - Moszkva, Szentpétervár, Nyizsnyij Novgorod, Kijev: Péter, 2016. - (A számítástechnika klasszikusai). - ISBN 978-5-496-01545-5 BBC 32.973.2-018.
Michael Ian Shamos, Dan Hoey. Legközelebbi problémák // Proc. 16. éves IEEE szimpózium a számítástechnika alapjairól (FOCS). - 1975. - doi : 10.1109/SFCS.1975.8 .
Fortune S., Hopcroft JE Megjegyzés Rabin legközelebbi szomszéd algoritmusához // Information Processing Letters. - 1979. - T. 8 , sz. 1 .
Clarkson KL 24. éves szimpózium a számítástechnika alapjairól. – 1983.
Khuller S., Matias Y. Egy egyszerű randomizált szita-algoritmus a legközelebbi pár problémájára // Inf. Comput. - 1995. - T. 118 , sz. 1 .
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid. Véletlenszerű adatszerkezetek a dinamikus legközelebbi pár problémához // SIAM J. Comput. . - 1998. - T. 26 , 4. sz . Az előzetes változatot a „4th Annu. ACM-SIAM Symp. on Discrete Algorithms", 1993, 301-310
Sergey N. Bespamyatnikh. Optimális algoritmus a legközelebbi páros karbantartáshoz // Discrete Comput. Geom. - 1998. - Kiadás. 19 .
UCSB előadási jegyzetek
rosettacode.org – Több programozási nyelven megvalósított legközelebbi pontpár
Vonalsöprés algoritmus a legközelebbi pár problémára