20.500.12556/DKUM-19843 INKREMENTALNO ISKANJE NAJBLIŽJE TOČKE S TRINIVOJSKIM RAZVRŠČANJEM TOČK V RAVNINI INCREMENTAL NEAREST-POINT SEARCH WITH THREE-LEVEL POINT ARRANGEMENT IN PLANE V 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. In this thesis, we present a new algorithm for solving the incremental nearest-point problem. Some of the known solutions to date failed to provide competitive results in situations when the initial set of points is unequally dispersed over the plane. Further, the algorithm which splits the plane on equal strips and was intended to solve those situations can quickly run into sets of points where it was proven ineffective. The idea from the very same beginning was to combine both methods into three-level point arrangement but we did not get the desired result at the end. Thus, we present a new approach that applies the idea of dynamic two-way plane splitting. We arrange the points into horizontal and vertical strips, each strip containing two deterministic skip lists for storing the x and y coordinates of a point respectively. The nearest-point search is executed simultaneously among up to eight DSLs. The new solution meets our expectations and is often considered as better alternative to the best-known solutions to date. inkrementalni problem najbližje točke sekljalna tabela deterministični seznam s preskakovanjem (DSL) iskanje najbližje točke dvosmerna dinamična delitev ravnine na trakove razpolavljanje DSL trinivojsko razvrščanje točk incremental nearest-point problem hash table deterministic skip-list (DSL) nearest-point search dynamic two-way plane splitting DSL splitting three-level point arrangement true true false [T. Dimkov] Slovenski jezik Angleški jezik Diplomsko delo 2011-08-31 13:04:51 2011-09-05 08:58:23 2022-04-13 15:42:09 2023-12-26 03:15:58 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.925:514.113(043.2) 15300118 URN:SI:UM:DK:NWPQ0DPW UNI_Dimkov_Tose_2011.pdf UNI_Dimkov_Tose_2011.pdf 1 841FD4520B47F71C98803E6F38DE9B2B db8d83b31e3dad10c0d2f7d62894f45026227cf5f54fc6db611e7769c9558560 79ce7b66-7c05-11eb-bb7a-00155d0001ca 20.500.12556/dkum/1285eaf1-cb7d-40b7-ad3f-0c2ef1257e2a https://dk.um.si/Dokument.php?lang=slv&id=24423 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0