Geometriai algoritmusok elõadás

Idei Tételsor: pdf
Elekes György jegyzete: pdf ps.gz
Saját, nagyon zavaros vázlatom az idei elõadásokról: txt (bárkiét szívesen felteszem)

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

Utolso ora:
k-szint es k-set, becslesek
crossing lemma es alkalmazasa

Tizenegyedik ora:
konvex burok 3d-bol hianyzo resz bize
dualitas es V-diag kapcsolata konvex burokkal
Davenport-Schinzel sorozatok es also szint kiszamitasa

Tizedik ora:
poliederek bonyolultsaga es terfelbontas
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

Kilencedik ora:
Delaunay-haromszogeles kiszamitasa nlog n ideju RND algoritmussal
alkalmazas: minimalis euklideszi feszitofa kereses
mese konvex burokrol magasabb dimenzioban

Nyolcadik ora:
diszkrepancia kiszamitasa felsikokra n^2 idoben
Jo haromszogelesek es Delaunay-haromszogeles

Hetedik ora:
Farthest point Voronoi-diagramm tulajdonsagai es kiszamitasa
alkalmazas: smallest width annulus kiszamitasa
parabolikus dualitas

Hatodik ora:
Voronoi-diagramm tulajdonsagai es kiszamitasa

Otodik ora:
ontes 2 es 3 dimenzioban
felsikok metszetenek meghatarozasa nlog n, uresseguk tesztelese RND n idoben
minimalis tartalmazo kor kereses RND n idoben

Negyedik ora:
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
sikdarabolas szamolasa egyenesekre n^2 idoben

Harmadik ora:
ket sikgraf kozos finomitasa - nlog n idoben (n az output bonyolultsaga)
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

Masodik ora:
hogyan szamoljuk ki n db egysegkor konvex burkat? (konvex burok+egysegkor)
also korlat 2 dim konvexre: Yao, Ben-Or: mind az n pont konvex burkon-e is \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
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

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
Ben-Or tetel gyenge verzioja: n szamrol megallapitani, hogy mind kul-e min nlog n linearis teszt