Geometriai algoritmusok elõadás

Péntek 1200-1330, Déli tömb 4-428 Paál Árpád terem
Tételsor: .pdf
Régi honlap: .html

Ajánlott olvasmány:
de Berg, van Kreveld, Overmars, Cheong (Schwarzkopf): Computational Geometry, Springer, 3rd ed. 2008.

Tizedik (es egyben utolso) ora:
Davenport-Schinzel sorozatok es also szint kiszamitasa
k-szint es k-set, becslesek
crossing lemma es alkalmazasa

Kilencedik ora:
konvex burok 3d
szupertrivi: minden pontotoshoz megnezzuk konvex-e - n^5 ido
csomagkotozo (Jarvis march): hn ido
veletlen algoritmus: nlog n ido
Chan output erzekeny alg: nlog h ido
kell hozza poliederek Dobkin-Kirkpatrick hierarchiaja

Nyolcadik ora:
Delaunay-haromszogeles kiszamitasa nlog n ideju RND algoritmussal
alkalmazas: minimalis euklideszi feszitofa kereses
dualitas es V-diag kapcsolata konvex burokkal
poliederek bonyolultsaga es terfelbontas
konvex burok magasabb dimben

Hetedik ora:
parabolikus dualitas
diszkrepancia kiszamitasa felsikokra n^2 idoben
Jo haromszogelesek es Delaunay-haromszogeles

Hatodik ora:
minimalis tartalmazo kor kereses RND n idoben
Farthest point Voronoi-diagramm tulajdonsagai es kiszamitasa
alkalmazas: smallest width annulus kiszamitasa

Otodik ora (Keszegh Balazs):
felsikok metszetenek letezesenek tesztelese RND n idoben
Voronoi-diagramm tulajdonsagai es kiszamitasa nlog n idoben

Negyedik ora:
sikdarabolas szamolasa egyenesekre n^2 idoben
ontes 2 es 3 dimenzioban
felsikok metszetenek meghatarozasa nlog n idoben

Harmadik ora:
art gallery problem: [n/3] or szukseges es elegseges
y-monoton sikdarabolasok es haromszogeles nlog n idoben
art galleryrol meg tobb itt: http://maven.smith.edu/~orourke/books/ArtGalleryTheorems/art.html
hogyan dontsuk el, hogy adott sikdarabolas melyik lapjan van egy pont? megoldasok szamokra
elso mo n^2 eloprocessz es log^2 n keressel, majd javitas nlog n elopr es log n keresesre

Masodik ora:
hogyan szamoljuk ki n db egysegkor konvex burkat? (konvex burok+egysegkor)
szakaszok metszespontjainak kiszamolasa sopressel - (n+h)log n idoben:
http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
kiegyensulyozott binaris keresofa (biz nelkul)
sikdarabolas/geometriai sikgraf tarolasa duplan lancolt listaval
ket sikgraf kozos finomitasa - nlog n idoben (n az output bonyolultsaga)

Elso ora:
"bevezetés" adatstruktúrákba: tömbök, láncolt listák
tobbnyire nem reszletezzuk, de neha szukseg lesz vmi trukkosebbre
altalanos helyzet es perturbacio
konvex burok
szupertrivi: minden pontnegyeshez megnezzuk konvex-e - n^4 ido
trivi: minden ir. elhez megnezzuk, hogy hataron-e - n^3 ido
csomagkotozo (Jarvis march): also es felso burkot kulon keressuk, novekvo x-koord szerint - hn ido
pontok egyenkent: ha mar rendezve vannak pontok x-koord szerint, akkor n ido - "amortizacios" ido
divide et impera: ez is n ido, szamolas uugy, mint elobb
Chan output erzekeny alg: nlog h ido http://en.wikipedia.org/wiki/Chan%27s_algorithm
Yao, Ben-or: annak eldontese, hogy mind az n pont konvex burkon-e \Omega(nlogn)
elotte: n szam mind kulonboze-e eldontese is \Theta(nlogn)
Thom-Milnor tetel (biz nelkul) es nemlinearis kerdesekre is biz nelkul
akit erdekel, lasd reszleteket itt: people.bath.ac.uk/masnnv/Teaching/AAlg11_8.pdf
rendtipus definicioja