Geometriai Algoritmusok elöadás IV-V. matematikusoknak

2005 tavasz



Csütörtök 14-16, Déli tömb 3-607 (MEGVÁLTOZOTT HELYEN!!!)

1. elöadás (febr. 17)

Ismétlés: tömbök, listák elönyei és hátrányai.
Bevezetö példa: maximális konvex sokszög keresése dinamikus programozással, O(n³) tárral, O(n4) idöben.
Konvex burok a síkban :
A csomag-kötözö algoritmus O(k n) idöben, ahol ,,k" a burok csúcsainak száma (,,output-érzékeny" algoritmus);
Egyenkénti hozzávétellel O(n log n) idöben.

2. elöadás (febr. 24)

Konvex burok a síkban (folytatás): ,,oszd meg és uralkodj"
Konvex burok a térben (vázlat):
itt is ,,oszd meg és uralkodj", csomagkötözéssel kombinálva.
Általános helyzet szimulálása (,,szimbolikus perturbáció'').
Momentum-görbe. Konvex poliéderek sok éllel, lappal, hiperlappal, ...
Következmény: d-dimenzióban nincs (n[d/2])-nél gyorsabb algoritmus.
Alsó becslések a síkban:
Ha az eredmény (ciklikusan) rendezett;
ha csak az a kérdés: minden pont csúcs-e.
Algebrai döntési fák. Ben-Or tétele (elötte: ,,kis"-Ben-Or tétel)

3. elöadás (márc. 3)

Ben-Or tételek bizonyítása
Chan-féle ,,output-érzékeny" algoritmus 2D konvex burokra.

4. elöadás (márc. 10)

Síkdarabolás tárolása: csúcsok, élek, lapok + mutatók.
Síkdarabolás egyenesekkel.
Az adatstruktúra építése O(n² log n) idöben rendezésekkel.
építés O(n²) idöben (,,új egyenes lemmája").
Dualitás (parabolikus). Alaptulajdonságok.
Példa: Gallai tétel duálisa.

5. elöadás (márc. 17)

Konvex sokszög (csúcshalmazának) duálisa: homokóra.
Maximális homokóra keresése dinamikus programozással (élek számozásával), O(n²) tárral, O(n³) idöben.
Következmény: maximális konvex sokszög kereshetö ugyanígy.
Pont helyének visszakeresése síkdarabolásban -- spec. esetek:
egyetlen adott konvex sokszögbe esik-e a pont?
egy adott, nem feltétlenül konvex sokszögbe esik-e?
visszakeresés tetszöleges síkdarabolásban O(n) idöben.
Az igazi probléma: adott síkdarabolás ,,elö-feldolgozása" úgy, hogy tetszöleges pontról gyorsan [azaz o(n) idöben] eldönthessük, melyik lapra (esetleg élre/csúcsba) esik.

6. elöadás (márc. 31)

A ,,sávos" adatstruktúra: O(n²) tár, O(log n) visszakeresési idö.
Monoton síkdarabolások.
Szükséges és elégséges feltétel.
Monotonná tevés O(n) él hozzévételével (söprés + dinamikusan kiegyensúlyozott fák, pl. 2-3 fák).
Az ,,alá nyúlik" reláció antiszimmetrikus és körmentes (de nem feltétlenül tranzitív).
Lapok rendezése ,,alulról felfelé".

7. elöadás (április 7)

Monoton síkdarabolások (folyt).
Egy (ötletes, de nem túl jó idejü) módszer: bináris keresés szeparáló élsorozatok között
Fokozatos javítás O(n) tárig és O(log n) idöig.
A posta-probléma.
Voronoi diagramm és elemi tulajdonságai.

8. elöadás (április 21)

Voronoi diagramm (folyt)
A d-dimenziós VD-keresés visszavezetése (d+1)-dim konvex burokra.
Algoritmus O(n log n) idöben.
Delaunay-háromszögelés (VD duálisa). Algoritmus O(n log n) idöben.
Ekvivalens definíció.
,,Jó" négyszögek és a négyszög-javítás.
Négyszög-javítások tetsz. sorozata véges.
Ehhez LEMMA: az elöforduló szögek (nem csökkenö sorrendü) vektora lexikografikusan szig. nö.
MESE: véletlen algoritmus: A pontokat véletlen sorrendben vesszük az eddigiekhez és javítunk, ameddig kell. Várható lépésszám: O(n log n).

9. elöadás (április 28)

A legközelebbi szomszédok gráfja. Algoritmus O(n log n) idöben.
Euklideszi minimális feszítö fa O(n log n) idöben.

10. elöadás (május 5)

Davenport-Schinzel sorozatok.
D_1(n) = n, D_2(n) = 2n-1, D_3(n) = O (n * α(n)).
(Utóbbi nem biz; csak D_3(n) = O (n * log n) volt.)
A továbbiak is ,,majdnem lineárisak".
r-paraméteres függvénygörbe-seregek:
az alsó burkoló ívei
DS(n,r) sorozatot alkotnak, ha a függvények R-en értelmezettek;
DS(n,r+2) sorozatot, ha intervallumokon.
Az állítás megfordítása.

10. elöadás (május 12)

r-paraméteres függvénygörbe-seregek (folytatás):
Felsö korlát egy lap bonyolultságára.
Síkdarabolás építése ,,lényegében O(n²) idöben" (ehhez: új görbe lemmája).