Triangulacija enostavnega večkotnika v linearnem časuTesten, Tomo (Avtor) Kanduč, Tadej (Mentor) triangulacija enostavnega večkotnikaračunalniška geometrijamonotoni večkotnikialgoritem pometanjaSeidelov algoritemChazellov algoritemV 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.20252025-09-12 13:20:00Diplomsko delo/naloga173072VisID: 38214COBISS_ID: 252917507sl