diplomsko delo
David Balažic (Author), Borut Žalik (Mentor)

Abstract

Iskanje najbližje točke je temeljni problem v računalniški geometriji. Diplomsko delo obravnava Bentleyev algoritem z delitvijo prostora na celice v različici za 3D prostor ter razširitev z rekurzivno delitvijo celic na podcelice. Algoritem je preizkušen na različnih množicah točk, tako sintetičnih kot praktičnih. Za primerjavo so testirani tudi naivna metoda iskanja ter metoda z osmiškim drevesom. Ugotovljeno je, da je Bentleyev algoritem učinkovit na različnih vhodnih podatkih in ima v večini primerov linearno časovno zahtevnost tako pri predobdelavi podatkov kot pri iskanju vseh najbližjih sosedov. Metoda z rekurzivno delitvijo celic izboljša hitrost iskanja na množicah z močno neenakomerno porazdelitvijo točk v prostoru, kjer prejšnja dosega slabše rezultate.

Keywords

algoritmi;računalniška geometrija;najbližja točka;delitev prostora;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher: D. Balažic
UDC: 004.921.021(043.2)
COBISS: 19466006 Link will open in a new window
Views: 1010
Downloads: 72
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: THE CLOSEST POINT SEARCH IN 3D SPACE
Secondary abstract: A closest point search is a basic problem in the computational geometry. This diploma thesis deals with the Bentley cell-based space partitioning algorithm and an extension of it with recursive subdivision of the cells. The algorithm is tested on different point distributions in the 3D space, both synthetic and from the real world. For comparison the naive method and an octree-based method were also tested. It was found that the Bentley algorithm performs well on different datasets and in most cases has a linear time complexity both for preprocessing and searching all nearest neighbors. The recursive method improves searching speed on inputs with strongly non-uniform distributions, where the former algorithm performs worse.
Secondary keywords: algorithm;computational geometry;closest point;spatial subdivision;
URN: URN:SI:UM:
Type (COBISS): Undergraduate thesis
Thesis comment: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informatika
Pages: X, 34 str., [32] pril.
ID: 9128108
Recommended works:
, diplomsko delo
, diplomska naloga univerzitetnega študijskega programa
, diplomsko delo
, diplomska naloga univerzitetnega študijskega programa
, no subtitle data available