Geometriai algoritmusok előadás

Tételsor: pdf
Elekes György jegyzete: pdf ps.gz
Saját, nagyon zavaros vázlatom az 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.

Tizenharmadik ora:
Euklideszi min feszitofa
konvex burok kereses 3d-ben
konvex burok dualisanak kapcsolata Voronoi-diagrammal

Tizenkettedik ora:
D-haromszogeles kiszamitasara kozvetlen RND algoritmus
(futasido bize nelkul)
konvex burok magasabb dimben

Tizenegyedik ora:
farthest-point Voronoi-diagramm kiszamitasa RND algoritmussal
alkalmazas: smallest width annulus
domborzati terkep keszites, jo haromszogeles, Delaunay haromszogeles alaptulajdonsagai

Tizedik ora:
Voronoi-diagramm kiszamitasa Fortune's algoritmusaval
pontok helyett intervallumok, alkalmazas
farthest-point Voronoi-diagramm

Kilencedik ora:
also burkolo szamitasa es Davenport-Schinzel sorozatok
Voronoi-diagramm alaptulajdonsagai

Nyolcadik ora:
crossing lemma
Dey felso korlatja felezoegyenesek szamara


Hetedik ora:
diszkrepancia szamitasa felsikokra ha pontok negyzetben dualitassal n^2 idoben
k-level es k-set, egyszeru also es felso korlatok

Hatodik ora:
minimalis tartalmazo kor kereses RND n idoben
parabolikus dualitas
diszkrepancia

Otodik ora:
sikdarabolas kiszamolasa n egyenesre n^2 idoben
ontes 2 es 3 dimenzioban
felsikok metszetenek meghatarozasa nlog n, uresseguk tesztelese RND n idoben

Negyedik ora:
hogyan dontsuk el, hogy adott sikdarabolas melyik lapjan van egy pont?
elotte: hogyan dontsuk el, hogy melyik ket szam kozott van egy uj szam?
javitas linearis tarra n es log n keresesi idore

Harmadik ora:
sikdarabolas/geometriai sikgraf tarolasa duplan lancolt listaval
ket sikgraf kozos finomitasa - nlog n idoben (n az output bonyolultsaga)
teremor/art gallery problema: [n/3] kell es talalhato is nlog n idoben
hozza: monoton sikfelbontas es haromszogeles
errol minden: 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)
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)

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

A tantárgy tervezett tematikája:
Konvex burok síkban
Alsó korlátok konvex burok keresésre döntési fákkal, d-dim alsó korlátok
Síkdarabolás számítása és tárolása, monoton síkdarabolás
Dualitás - homokóra és nagy konvex sokszög keresése
Voronoi-diagram és Delaunay háromszögelés