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

2006 tavasz

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(n³) tárral, O(n⁴) 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(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 (április 25)

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(n²) tárral, O(n³) 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(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 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ö.

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.