| KRATKA VSEBINA | The report introduces a new algorithm for constructing a 2D Delaunay triangulation. It bases on the sweep-line paradigm, which is combined by a local optimisation criterion - a caracteristic of the incremental insertion algorithms. The sweep-line status is represented by so-called advancing front, which is implemented asa hash-table. To prevent the construction of tiny triangles, which would begenerated by a direct implementation of the sweep-line approach, heuristicshave been introduced. The algorithm has been compared with other popular Delaunay algorithms: improved Gubais, Knuth, and Sharir's incremental algorithm, Žalik and Kolingerova randomised incremental algorithm using two-level uniform space subdivision, Muecke's et al randomised incremental walking algorithm, Lee and Schachter's divide and conquer algorithm, and Fortune's sweep-line algorithm. Schewchuk's implementation of the last three algorithms has been used. The proposed algorithm is for at last 400% faster that fastest algorithm among tested ones. Beside that, the algorithmdoes not use a lot of memory for supporting data structure, it is easy to understand and simple to implement. All of that align the proposed algorithm among the best algorithms for constructin Delaunay triangulation.// V poročilu opišemo nov algoritem za konstrukcijo ravninske Delaunayeve triangualcije. Algoritem temelji na uporabi prebirne premice, ki ga kombiniramo z lokalno optimizacijo - značilnost inkrementalnih naključnih algoritmov. Na ta način dobimo algoritem, ki v mnogočem posnema akcije človeka pri ročni konstrukciji Delaunayeve triangulacije. Stanje prebirne premice predstavlja tako imenovana napredujoča fronta, ki jo implementiramokot sekljalno tabelo. Da se izognemo konstrukciji ozkih trikotnikov, ki jihdobimo pri neposredni uporabi postopka prebirne premice, smo uvedli preproste heuristike. Algoritem smo primerjali z drugimi znanimi algoritmi:izboljšanim Gubaisovim, Knuthovim in Sharirovim inkrementalnim, Žalikovim in Kolingerovim naključnim inkrementalnim algoritmom z uporabo dvonivojske enakomerne delitve prostora, Mueckejevim et al inkrementalnim naključnim algoritmom s sprehajanje, Leejevim in Schachterjevim algoritmom z metodo deli in vladaj in Fortuneovim algoritmom s prebirno premico. Izkaže se, da je predlagan algoritem za 400% hitrejši od najhitrejšega izmed preostalih algoritmov. Poleg tega je prostorsko nezahteven, enostaven za razumevanje in implementacijo. Vse te lastnosti ga uvrščajo med najboljše algoritme za konstrukcijo Delaunayeve triangulacije. |