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

2006 tavasz



Kedd 1030-12, Déli tömb 4-202

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

Ismétlés: tömbök, listák elönyei és hátrányai.
Bevezetö példa: nagy konvex sokszögek
létezése: a ''happy end'' probléma (Erdös-Szekeres tétel);
keresése dinamikus programozással, O(n3) 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. 21)

Konvex burok a síkban (folytatás): ,,oszd meg és uralkodj".
Konvex burok a térben (mese):
itt is ,,oszd meg és uralkodj", csomagkötözéssel kombinálva.
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 (febr. 28)

Momentum-görbe. Konvex poliéderek sok éllel, lappal, hiperlappal, ...
Következmény: d-dimenzióban nincs (n[d/2])-nél gyorsabb algoritmus.
Síkdarabolás tárolása: csúcsok, élek, lapok + mutatók.
Több dim: hasonlóan.
O (n[(d+1)/2]) idejü d-dimenziós konvex burok algoritmus.

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

Síkdarabolás egyenesekkel.
Az adatstruktúra építése O(n2 log n) idöben rendezésekkel.
Építés O(n2) idöben (,,új egyenes lemmája").
Dualitás (parabolikus). Alaptulajdonságok.
Példa: Gallai tétel duálisa.

5. elöadás (április 25)

Elmaradt :((

6. (pót)elöadás (április 26)

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(n2) tárral, O(n3) idöben.
Következmény: maximális konvex sokszög kereshetö ugyanígy.
A térbeli dualitás egy tulajdonsága.

7. elöadás (május 2)

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.
A ,,sávos" adatstruktúra: O(n2) 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 számozása ,,alulról felfelé".

8. elöadás (május 9)

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.

9. (pót)elöadás (május 10)

A posta-probléma.
Voronoi diagramm és elemi tulajdonságai.
A d-dimenziós VD-keresés visszavezetése (d+1)-dim konvex burokra.
Algoritmus a síkban O(n log n) idöben.
Delaunay-háromszögelés (VD duálisa). Algoritmus O(n log n) idöben.
Ekvivalens definíció.

11. elöadás (május 17)

Delaunay-háromszögelés (folyt):
,,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).
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.