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

diplomsko delo univerzitetnega študijskega programa

Toše Dimkov (Author), David Podgorelec (Mentor), Borut Žalik (Co-mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[T. Dimkov]
UDC:	004.925:514.113(043.2)
COBISS:	15300118
Views:	1891
Downloads:	141
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Incremental nearest-point search with three-level point arrangement in plane
Secondary abstract:	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.
Secondary keywords:	incremental nearest-point problem;hash table;nearest-point search;dynamic two-way plane splitting;three-level point arrangement;
URN:	URN:SI:UM:
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Medijske komunikacije
Pages:	IV, 29 f.
Keywords (UDC):	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