diplomsko delo
Jordan Lesjak (Avtor), Borut Robič (Mentor)

Povzetek

Konveksno ovojnico množice točk v ravnini si lahko predstavljamo kot najmanjši konveksen poligon, ki obdaja celotno množico. Računanje konveksne ovojnice je v praksi pogosta operacija in ima uporabo na številnih področjih stroke. V tem diplomskem delu so predstavljeni in analizirani številni tradicionalni in moderni algoritmi za izračun konveksne ovojnice v dvodimenzionalnem Evklidskem prostoru, ki so nato ovrednoteni na podlagi različnih praktičnih performančnih testov. Bolj podrobno je predstavljen algoritem Ordered hull, ki se je izkazal za bistveno hitrejšega od algoritma Quickhull, ki je dolgo časa veljal za najhitrejšega.

Ključne besede

konveksna ovojnica;ravnina;algoritem;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Lesjak]
UDK: 004(043.2)
COBISS: 65721091 Povezava se bo odprla v novem oknu
Št. ogledov: 359
Št. prenosov: 62
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Overview and comparison of convex hull algorithms
Sekundarni povzetek: The convex hull of a planar point set is the smallest convex polygon enclosing the entire set. Computing the convex hull is a fundamental operation with uses in several different fields of research. In this thesis, we explore several different traditional and modern algorithms for computing the convex hull in two dimensional Euclidean space. The algorithms are then evaluated through several different practical performance tests. Algorithm Ordered hull is described in greater detail, as it proved to be significantly faster than Quickhull, which is commonly regarded as the fastest algorithm for the problem.
Sekundarne ključne besede: convex hull;plane;algorithm;computer and information science;diploma;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000468
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 60 str.
ID: 12977412
Priporočena dela:
, bachelor's thesis
, diplomsko delo
, diplomsko delo