INKREMENTALNO ISKANJE NAJBLIŽJE TOČKE S TRINIVOJSKIM RAZVRŠČANJEM TOČK V RAVNINIDimkov, Toše (Avtor) Podgorelec, David (Mentor) inkrementalni problem najbližje točkesekljalna tabeladeterministični seznam s preskakovanjem (DSL)iskanje najbližje točkedvosmerna dinamična delitev ravnine na trakoverazpolavljanje DSLtrinivojsko razvrščanje točkV diplomskem delu je predstavljen nov algoritem za reševanje inkrementalnega problema najbližje točke v ravnini. Predhodna rešitev z enakomerno delitvijo ravnine na trakove se ni obnesla v primeru izrazito neenakomerno porazdeljenih točk, pa tudi njena izboljšava z enosmernim dinamičnim pristopom delitve na trakove lahko v praksi hitro naleti na porazdelitve točk, kjer se izkaže za neučinkovito. Prvotna ideja je bila zgolj kombinirati oba pristopa v trinivojsko organizacijo točk, a nismo bili povsem zadovoljni z rezultati, zato v delu predlagamo tudi nov pristop z dvosmerno dinamično delitvijo na trakove. Tako v horizontalnih kot v vertikalnih trakovih organiziramo točke v po dva deterministična seznama s preskakovanjem (DSL), iskanje točke pa potem poteka sočasno z izmenično rabo do osmih DSL. Nova rešitev doseže cilj, za katerega je bila zasnovana, in pogosto predstavlja boljšo alternativo kot do sedaj obstoječi algoritmi. [T. Dimkov]20112011-08-31 13:04:51Diplomsko delo19843sl