Domov > Obvestila > Andrej Brodnik: Ali je 2 x 1D boljše od 2D?

Andrej Brodnik: Ali je 2 x 1D boljše od 2D?

Datum objave: 2. 4. 2008
Vir: Seminar za teorijo grafov in algoritme
Thursday, April 3, 2008, at 12:15 in room PS, Jadranska 19

    Andrej Brodnik, Mirko Zadravec, Borut Žalik.

Problem iskanja najbližjega soseda s svojimi izvedenkami je eden temeljnih problemov, ki jih srečujemo v računalniški geometriji (computational geometry). V tem predavanju si bomo najprej pogledali reševanje v eni dimenziji ter nato še v dveh dimenzijah. V obeh primerih si bomo pogledali tudi vpliv dejstva, da so lahko točke izbrane iz neke končne univerzalne množice.

V eno-razsežnostni inačici je problem poznan tudi pod imenom posplošeni slovar (generalized dictionary) in si bomo ogledali dve različici in sicer statično in dinamično.

Večina predavanja bo namenjena dvo-razsežnostnemu problemu. Omenili bomo nekaj osnovnih tehnik za reševanje problema v dveh razsežnostih – k-d drevesa. Nato se bomo vrnili k uporabi hierarhije preprostih rešitev iz ene razsežnosti. V tej tehniki razdelimo elemente v pasove v eni razsežnosti in nato elemente vsakega pasu ponovno shranimo v eno-razsežnostni podatkovni strukturi – npr. RČ-drevesa, (a,b)-detereministične preskočne vrste ali (a,b)-drevesa.

Omenjene rešitve smo empirično ovrednotili v tako imenovanem problemu iterativnega iskanja: t.j., za vsako točko p: vstavi točko p v strukturo in poišči tej točki najbližjo točko, ki je že v strukturi. Čeprav ima naša tehnika najslabši čas izvajanja O(n) za eno vstavljanje oziroma iskanje ter posledično O(n2) za vstavljanje n točk, se izkaže v empiričnih testih na različnih množicah sintetičnih in pravih podatkov iz GIS podatkovnih baz, da je učinkovitejša od prej omenjene rešitve, ki je bila načrtovana specifično za dvo-razsežnostni prostor.

Iz povedanega lahko sklepamo, da analiza najslabše možnosti (worst case analysis) verjetno ni primerna, ampak da bi se morali lotiti povprečne ali amortizirane analize, da lahko pojasnimo naš empirični rezultat.