20.500.12556/DKUM-45072 APROKSIMACIJSKI ALGORITEM GRADNJE SREDNJE OSI ENOSTAVNIH MNOGOKOTNIKOV, TEMELJEČ NA OMEJENI DELAUNAYEVI TRIANGULACIJI APPROXIMATION ALGORITHM FOR MEDIAL AXIS COMPU-TATION ON SIMPLE POLYGONS USING CONSTRAINED DELAUNAY TRIANGULATION V doktorski disertaciji uvedemo nov postopek gradnje aproksimativne srednje osi, ki je učinkovitejši od obstoječih metod. Naprej opredelimo problem, področja upo-rabe in podamo hipotezi. V nadaljevanju na kratko razložimo Voronoijev diagram in opozorimo na povezavo med njim in Delaunayjevo triangulacijo, ki jo razširimo še z opisom omejene Delaunayjeve triangulacije. Zatem se osredotočimo na algoritme gradnje srednje osi, ki jih delimo na eksaktne in aproksimacijske. Sledijo definicije in pregled dosedanjih rešitev. V jedru doktorske disertacije opišemo nov algoritem za konstrukcijo aproksimacije srednje osi mnogokotnika. V tem poglavju opišemo naš algoritem za triangulacijo enostavnega mnogokotnika, uporabljeno hevristiko in korak generiranja srednje osi iz središč dobljenih trikotnikov. Sledi analiza algoritma, kjer izpeljemo prostorsko in časovno zahtevnost, in primerjava našega algoritma z obstoje-čimi metodami. Razvijemo tudi novo metriko za oceno kakovosti aproksimacije. Dok-torsko disertacijo zaključimo s pregledom opravljenega dela in opozorimo na izvirne znanstvene prispevke. In this doctoral dissertation a new method for approximating a polygon’s medi-al axis is introduced. As shown by experiments, the new method is more efficient than the existing methods. Firstly the definition of the main problem is given. This is fol-lowed by the description of fields, where the medial axis is used, and finished with the hypotheses. In the next chapter, the connection between the Voronoi diagram and the Delaunay triangulation is mentioned, which is followed by the description of the con-strained Delaunay triangulation. In the next chapter, algorithms for medial axis con-struction are described and classified into groups of exact and approximate algo-rithms. This is followed by definitions and an overview of existing methods. The core of this doctoral dissertation is composed of the description of a new algorithm for medial axis construction of a simple polygon. In this chapter, the triangulation, heuristics and the step for medial axis construction out of the triangles circumcentres are described. The next chapter is devoted to the analysis of our algorithm. Here the time and space complexity are derived and the comparison of our algorithm with the existing ones is given. This is followed by the description of a metric, which evaluates the exactness of a polygon’s medial axis. The doctoral dissertation is concluded with evaluation of the hypotheses and an overview of the scientific contributions. računalniška geometrija algoritmi skeleton srednja os omejena Delaunayjeva trian-gulacija Steinerjeve točke computer geometry algorithms skeleton medial axis constrained Delaunay triangu-lation Steiner points true true false G. Smogavec] Slovenski jezik Angleški jezik Doktorska disertacija 2014-07-31 22:07:16 2014-08-19 14:24:41 2022-05-14 03:07:22 2021-05-01 03:19:37 2014 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.925.8(043.3) 18055958 URN:SI:UM:DK:MXECKZ7L DR_Smogavec_Gregor_2014.pdf DR_Smogavec_Gregor_2014.pdf 1 777F99DFCF6EC780781347AC47CA73CF 20320e8750c1dfd3c43dbaf32a5c7f6d2e0d6e35e8844da13018b9569919111d 0222964a-7c0b-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=65069 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0