Računska geometrija

Pogojev za vključitev v delo ni.

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.

1. M. de Berg ... [et al.]. Computational geometry : algorithms and applications, 2nd, revised ed., Berlin : Springer, cop. 2000.
2. S. L. Devadoss, J. O’Rourke: Discrete and computational geometry, Princeton : Princeton University Press, cop. 2011.
3. J. O’Rourke: Computational geometry in C, 2nd ed., Cambridge : Cambridge University Press, 1998.

Študent nadgradi svoje poznavanje podatkovnih struktur in osnovnih algoritmov, ki se uporabljajo za algoritmično reševanje geometrijskih in sorodnih problemov.

Osnovni geometrijski objekti
Računanje z geometrijskimi podatki
Osnovne podatkovne strukture za geometrijske podatke
Osnovni algoritmi računske geometrije

Predavanja, seminar, vaje, domače naloge, konzultacije in samostojno delo študentov.

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)

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]