2.
ISKANJE NAJBLIŽJE TOČKE V 3D PROSTORUDavid Balažic, 2016, diplomsko delo
Opis: 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.
Ključne besede: algoritmi, računalniška geometrija, najbližja točka, delitev prostora
Objavljeno v DKUM: 18.03.2016; Ogledov: 1452; Prenosov: 95
Celotno besedilo (1,97 MB)