06 júna 2008

Najmenšia vzdialenosť dvoch bodov

V práci môjho bakalára sa vyskytol nasledovný okrajový, ale celkom zaujímavý algoritmický problém:

Vstupom je n vektorov x1,...,xn v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu

Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.

Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.

19 komentárov:

demiurge povedal(a)...

Pokiaľ si dobre spomínam, tak sme brali nejaký rýchly algoritmus na nájdenie minimálneho prvku množiny zrovnateľných prvkov, kde jediná povolená operácia je porovnanie dvoch prvkov. Ak chceš, môžem sa ti na to pozrieť.

demiurge povedal(a)...

Tak som sa na to pozrel. Existuje lineárny algoritmus vzhľadom k počtu prvkov postupnosti, a navyše dokáže zistiť v lineárnom čase i-ty (teda nie len najmenší) prvok postupnosti. Btw, Qsort a ostatné sorty pracujú s n.log(n), takže by nemal byť problém urobiť algoritmus minimálne s touto zložitosťou.

demiurge povedal(a)...

Tak sa ospravedlňujem, doplietol som to... Ide o to, že množina, z ktorej tu fakticky vychádzame, má veľkosť n(n-1)/2, čiže by som si to musel ešte premyslieť. Také jednoduché to zasa nie je, ako som si myslel.

kuko povedal(a)...

v 1D existuje linearny algoritmus: najdeme minimum, maximum a interval medzi nimi rozdelime na n casti (rovnako velkych podintervalov) a pre kazdy si zistime minimum a maximum; potom uz staci prejst po vsetkych castiach a pozerat minima maxima a ratat vzdialenosti...
v 2D existuje divide&conquer algoritmus beziaci v O(nlog n)
do vyssich dimenzii moje vedomosti velmi nesiahaju

Radoslav Harman povedal(a)...

kuko: Rozmýšľal som nad tým 1D algoritmom; vyzerá to byť veľmi zaujímavý trik, ale, bohužiaľ, nepochopil som ho. Nemohol by si ho opísať trochu presnejšie, alebo dať nejaký link? (Prípadne mi ho môže vysvetliť aj niekto iný, kto to pochopil :-)

Ja sám neviem skonštruovať v 1D na daný problém O(n) algoritmus, ale O(nlog(n)) je veľmi jednoduchý: stačí tie čísla usporiadať napríklad heapsortom, ktorý je O(nlog(n)) a potom už len porovnávať susedné prvky, čo je len O(n).

kuko povedal(a)...

mmmm... ok, popleta... to co som popisal funguje pre hladanie maximalnej vzdialenosti... pre minimalnu nepoznam nic rychlejsie ako O(nlog n)
btw co sa tyka maximalnej vzdialenosti v 2d, to ide tiez v O(nlog n) -spravime konvexny obal a tocime sa po obvode...

rasto povedal(a)...

K tomu 1D algoritmu:

ja ho poznam pre najdenie najvacsej vzdialenosti dvoch susednych bodov, neviem ako ho zmenit pre najmensiu vzdialenost, ale pre inspiraciu ta najvacsia je takto:

Ked viem ze medzi najlavejsim a najpravejsim bodom je vzdialenost x, tak rozdelenim na n intervalov dostanem kazdy interval velkosti x/n. A staci si potom uz len uvedomit ze najmensia najvacsia vzdialenost bude vacsia ako x/n, cize taky par bodov bude v roznych intervaloch .. a tak mi uz staci vzdy porovnat maximum predosleho itnervalu z minimum svojho intervalu.

Ta dynamika pre najmensiu a pre 2D je na:
http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

A pre zaujimavost, ako najst najvzdialenejsie dva body v manhatanovskej metrike? To bolo davnejsie na TopCoderovi ako najtazsia uloha: http://www.topcoder.com/stat?c=problem_statement&pm=6149&rd=9999&rm=249700&cr=13396848

kuko povedal(a)...

presnejsie: v 1d islo o problem najst maximalne vzdialene 2 susedne body... slubujem ze si rozmyslim kym daco napisem

nakoniec, nasiel som riesenie v O(nlog n):
www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
co je optimalne; prijemne citanie...

Radoslav Harman povedal(a)...

demiurge, kuko, rasto: Vyborne; tym sa to vsetko uz vyjasnilo. Nakoniec sa ukazalo, ze je to naozaj algoritmicky celkom zaujimavy problem.

Ja len dodam, ze s takouto ulohou sa da stretnut (z oblasti toho, comu sa trochu venujem) napriklad pri testovani generatorov nahodnych cisiel, alebo pri konstrukcii dendrogramu v hierarchickej analyze zhlukov.

Inak k tym popleteniam: Kazdy sa obcas dopletie, alebo pomyli; v tom sa ludia nelisia. Lisia sa vsak v tom, ci si to dokazu priznat, alebo nie.

Naviac, chyb sa neda vyvarovat, ak chce clovek prist na nieco nove. Je lepsie riskovat chybu ako nepovedat nic. Napada ma nasledovny citat od Einsteina: “Anyone who has never made a mistake has never tried anything new.”

demiurge povedal(a)...

Len samozrejme ide o to, aby sa človek nemýlil príliš veľa, lebo potom zamestnáva ostatných "výsledkami", ktoré nie sú správne. Ja som to písal z práce a fakt som nad tým nerozmýšľal. Nabudúce si nájdem aspoň 15 minút času. Za túto dobu sa človeku všeličo vyjasní.

misof povedal(a)...

U väčšiny týchto geometrických vecí funguje tzv. "curse of dimensionality" -- síce sa dajú nájsť algoritmy, ktorých asymptotická zložitosť je dobrá (ak sa dívame na dimenziu ako na konštantu), no v praxi majú pre veľkú dimenziu tie algoritmy taký veľký overhead, že je praktickejšie použiť naivný algoritmus, ktorý prezrie všetky možnosti.

Neviem presne, ako je to v tomto konkrétnom prípade, ten algoritmus, na ktorý dal kuko linku ešte vyzerá celkom nádejne...

Pavel Chalmovianský povedal(a)...

Problém najbližšieho páru sa dá optimálne v 2D riešiť aj pomocou Voronoiovho diagramu. Najbližší pár generuje hranu v tomto diagrame a je ich lineárne veľa (lebo je rovinný). Na zostrojenie diagramu treba O(n log n) operácií.

Radoslav Harman povedal(a)...

pavel: Myslím, že v 2D funguje aj tento postup: Stačí nájsť Delaunayovu trianguláciu, na čo existuje O(nlog(n)) algoritmus a tá myslím musí obsahovať spojnicu dvoch najbližších bodov. Mám ale tušenie, že ten Tvoj návrh a tento môj sú veľmi príbuzné.

Pavel Chalmovianský povedal(a)...

Hej. Delaunayova triangulacia je ako rovinný graf duálom ku Voronoiovmu diagramu. Pričom duálnu transformáciu vieme zabezpečiť v čase O(n), takže nič nestratíme ani nezískame.

Radoslav Harman povedal(a)...

pavel, misof: zdá sa, že tento problém je dosť bohatý a keď sa k tomu pridajú príbuzné témy ako Voronoiove diagramy a Delaunayova triangulácia, tak by z toho mohla byť vhodná téma na bakalársku prácu. Alebo, ako hlavnú tému by ste mohli vypísať buď Delaunayovu trianguláciu, alebo Voronoiove diagramy a toto tu by bola jedna z aplikácií.

Peter Richtárik povedal(a)...

A čo takto nasledovný problém:

Notácia:
x, d sú vektory v R^n.
(d,x) = d_1*x_1+...+d_n*x_n

Úloha:
Spomedzi všetkých bodov x takých že (d,x) = 1, nájdi ten ktorý minimalizuje hodnotu max_i |x_i|.

Inak: Nájdi bod x v nadrovine danej rovnicou (d,x) = 1 s najmenšou L_infty normou.

Radoslav Harman povedal(a)...

Peter: Ja by som použil klasický LP algoritmus (metoda VuŽaVeS). Ale ako Ťa poznám, Ty máš na to určite premyslenú nejakú oveľa efektívnejšiu metódu :)

Peter Richtárik povedal(a)...

Cez LP by to šlo, ale je to tak trošku overkill :-)

Som zvedavý na rôzne zaujímavé riešenia/prístupy. Tak mi napadlo že by som tento problémik mohol šupnúť na svoju stránku.... Trošku popracujem... a šúps... už sa aj stalo! Je to tu: http://predbarakom.wordpress.com

Čakám na zaujímavé postrehy!

PS: Rado, ako lákadlo Ti prezradím že tento problém má skryte niečo spoločné so štatistikou :-)

Radoslav Harman povedal(a)...

Peter: Už to riešenie tuším. Napíšem koment k Tvojmu postu na wordpresse.