Pogojev za vključitev v delo ni.
Računska geometrija
2026/2027
Program:
Interdisciplinarni magistrski študijski program 2. stopnje Računalništvo in matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
ECTS:
6
Jezik:
slovenski, angleški
Nosilec predmeta:
Izvajalec (kontaktna oseba):
Ure na teden – 1. ali 2. semester:
Predavanja
2
Seminar
1
Vaje
2
Laboratorij
0
Vsebina
Presečišča daljic. Algoritmi pometanja.
Večkotniki in triangulacije večkotnikov.
Konveksne množice. Algoritme za iskanje konveksne ovojnice točk v ravnini.
DCEL. Problem določanja položaja.
Voronojevi diagrami. Fortuneov algoritem.
Delaunayeva triangulacija.
Podatkovne strukture za točke.
Dualnost in razporeditve.
Temeljni literatura in viri
- M. de Berg ... [et al.]. Computational geometry : algorithms and applications, 2nd, revised ed., Berlin : Springer, cop. 2000.
- S. L. Devadoss, J. O’Rourke: Discrete and computational geometry, Princeton : Princeton University Press, cop. 2011.
- J. O’Rourke: Computational geometry in C, 2nd ed., Cambridge : Cambridge University Press, 1998
Cilji in kompetence
Študent nadgradi svoje poznavanje podatkovnih struktur in osnovnih algoritmov, ki se uporabljajo za algoritmično reševanje geometrijskih in sorodnih problemov.
Predvideni študijski rezultati
Osnovni geometrijski objekti
Računanje z geometrijskimi podatki
Osnovne podatkovne strukture za geometrijske podatke
Osnovni algoritmi računske geometrije
Metode poučevanja in učenja
Predavanja, seminar, vaje, domače naloge, konzultacije in samostojno delo študentov.
Načini ocenjevanja
Sprotno preverjanje (domače naloge, kolokviji in projektno delo).
Končno preverjanje (pisni ali ustni izpit)
5 - 10, pri čemer velja, da je pozitivna ocena od 6 - 10
Reference nosilca
Sergio Cabello Justo:
– CABELLO, Sergio, GIANNOPOULOS, Panos, KNAUER, Christian, ROTE, Günter. Matching point sets with respect to the Earth Mover's Distance. Computational geometry, ISSN 0925-7721. [Print ed.], 2008, vol. 39, iss. 2, str. 118-133 [COBISS-SI-ID 14450521]
– BERG, Mark de, CABELLO, Sergio, HAR-PELED, Sariel. Covering many or few points with unit disks. Theory of computing systems, ISSN 1432-4350, 2009, vol. 45, no. 3, str. 446-469 [COBISS-SI-ID 14900825]
– CABELLO, Sergio, KNAUER, Christian. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational geometry, ISSN 0925-7721. [Print ed.], 2009, vol. 42, iss. 9, str. 815-824 [COBISS-SI-ID 15160409]
