Inkrementalno iskanje najbližje točke s trinivojskim razvrščanjem točk v ravnini

diplomsko delo univerzitetnega študijskega programa

Toše Dimkov (Avtor), David Podgorelec (Mentor), Borut Žalik (Komentor)

Povzetek

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.

Ključne besede

inkrementalni problem najbližje točke;sekljalna tabela;iskanje najbližje točke;trinivojsko razvrščanje točk;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[T. Dimkov]
UDK:	004.925:514.113(043.2)
COBISS:	15300118
Št. ogledov:	1891
Št. prenosov:	141
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Incremental nearest-point search with three-level point arrangement in plane
Sekundarni povzetek:	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.
Sekundarne ključne besede:	incremental nearest-point problem;hash table;nearest-point search;dynamic two-way plane splitting;three-level point arrangement;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Medijske komunikacije
Strani:	IV, 29 f.
Ključne besede (UDK):	science and knowledge;organization;computer science;information;documentation;librarianship;institutions;publications;znanost in znanje;organizacije;informacije;dokumentacija;bibliotekarstvo;institucije;publikacije;prolegomena;fundamentals of knowledge and culture;propaedeutics;prolegomena;splošne osnove znanosti in kulture;computer science and technology;computing;data processing;računalniška znanost in tehnologija;računalništvo;obdelava podatkov;application-oriented computer-based techniques;računalniške tehnike za namensko rabo;aplikativno usmerjene računalniško podprte tehnike;computer graphics;računalniška grafika;mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;geometry;geometrija;
ID:	8761961