Pogojev za vključitev v delo ni.
Računska geometrija
2020/2021
Program:
Interdisciplinarni magistrski študijski program 2. stopnje Računalništvo in matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
Skupina:
A
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, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, 3. izdaja, Springer, 2008.
S. Devadoss, J. O’Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.
J. O’Rourke, Computational Geometry in C, 2. izdaja, 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
Način (pisni izpit, ustno izpraševanje, naloge, projekt):
Sprotno preverjanje (domače naloge, kolokviji in projektno delo)
Končno preverjanje (pisni ali ustni izpit)
Ocene: 6-10 pozitivno, 5 negativno (v skladu s Statutom UL)
Reference nosilca
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]
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, 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]
