20.500.12556/RUL-173072 Triangulacija enostavnega večkotnika v linearnem času Triangulating a Simple Polygon in Linear Time V diplomski nalogi obravnavamo problem triangulacije enostavnih večkotnikov, enega izmed temeljnih problemov v računalniški geometriji. Najprej so predstavljeni osnovni pojmi, ki tvorijo teoretično podlago za razumevanje obravnavane teme. Sledi pregled algoritmov za triangulacijo, od najpočasnejših do praktično najhitrejših: naivni algoritem, metoda rezanja ušes, monotona triangulacija s pometanjem, Kirkpatrick–Klawe–Tarjanov algoritem in Seidelov algoritem. Sledi glavno poglavje, v katerem povzamemo članek o Chazellovem algoritmu, ki edini teoretično doseže optimum in s tem predstavlja pomemben mejnik v raziskavah hitre triangulacije večkotnikov. This thesis addresses the problem of triangulating simple polygons, one of the fundamental problems in computational geometry. First, the basic concepts are introduced, providing the theoretical foundation for understanding the topic. A review of triangulation algorithms then follows, ranging from the slowest to the practically fastest methods: the naive algorithm, the ear-clipping method, monotone triangulation by sweeping, the Kirkpatrick–Klawe–Tarjan algorithm, and Seidel’s algorithm. The main chapter is devoted to summarizing Chazelle’s algorithm, which is theoretically optimal and represents an important milestone in the study of efficient polygon triangulation. triangulacija enostavnega večkotnika računalniška geometrija monotoni večkotniki algoritem pometanja Seidelov algoritem Chazellov algoritem triangulation of a simple polygon computational geometry monotone polygons sweeping algorithm Seidel’s algorithm Chazelle’s algorithm. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-09-12 13:20:00 2025-09-12 13:20:05 2025-11-02 03:54:34 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38214 252917507 Testen_Tomo_-_Triangulacija_enostavnega_veckotnika_v_linearnem_casu.pdf Testen_Tomo_-_Triangulacija_enostavnega_veckotnika_v_linearnem_casu.pdf 1 3DB7B25966E9E4A8C8E66286143D6D07 b72aacade21eb29a63e70670f225fdb00786356a0f208615f670f365630417a1 455a971c-8fca-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217240 Fakulteta za računalništvo in informatiko 0 0 0