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

2004 tavasz



Hétfö 10-12, 3-607

Vizsga: május 21, péntek 1/2 3. Helye: 3-508.

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

  • 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(n a negyediken) idöben.
  • (Elnezest, de a "html" NEM TUD!?!?!? negyedik hatvanyt irni.)
  • 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;
    2-3 fákkal.

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

  • Síkdarabolás egyenesekkel (folytatás): építés O(n²) idöben (,,új egyenes lemmája").
  • Dualitás (parbolikus). Alaptulajdonságok.
  • Példa: Gallai tétel duálisa.
  • Konvex sokszög (csúcshalmazának) duálisa: homokóra.

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

  • 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 keresése ugyanígy.
  • 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.

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

  • Konvex burok a síkban (folytatás): ,,oszd meg és uralkodj" O(n log n) idöben.
  • Mese: konvex burok a térben O(n log n) idöben.
  • 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)
  • Momentum-görbe. Konvex poliéderek sok csúccsal.
    Következmény: d-dimenzióban nincs (n a [d/2]-ediken)-nél gyorsabb algoritmus.

  • 5. elöadás (márc. 22)

  • A ,,felsö becslés tétel" gyenge és erös alakja (biz. nélkül).
  • Konvex burok d dimenzióban O(n a [(d+1)/2]-ediken + n log n) idöben.
  • 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. 29)

  • 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) pont és él hozzévételével.
  • Monoton síkdarabolásban az ,,alá nyúlik" reláció antiszimmetrikus és körmentes (de nem feltétlenül tranzitív).

  • 7. elöadás (ápr. 19)

    (folytatás)
  • Monoton síkdarabolás lapjainak rendezése ,,alulról felfelé"
  • 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.

  • 8. elöadás (ápr. 26)

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

  • 9. elöadás (máj. 3)

  • ,,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.

  • 10. elöadás (máj. 10)

  • 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. 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.
  • 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).

  • 11. elöadás (máj. 17)

  • Chan-féle ,,output-érzékeny" algoritmus 2D konvex burokra.
  • Degenerált esetek kezelése tetszöleges dimenzióban:
    véletlen perturbáció;
    determinisztikus perturbáció;
    szimbolikus perturbáció.