1. eloadas (szept 11.)

Sylvester sejtes - Gallai tetel
Parabolikus dualitas, dualis Gallai
Ramsey tetele (veges grafokra)

1. gyakorlat (szept 12.) feladatai (gzipped PS, 22K) --- Sikgrafok is voltak!

2. eloadas (szept 18.)

Erdös also becslese
Ramsey tetele halmazrendszerekre
A "happy end" problema
Algoritmus nagy konvex sokszogek keresesere dinamikus programozassal O(n3) tarral, O(n4) idoben.

2. gyakorlat (szept 19.) feladatai (gzipped PS, 27K)

3. eloadas (szept 25.)

Sikdarabolasok adatstrukturaja: csucsok, elek, lapok; rekordok, pointerek oda-vissza
Spec: sikdarabolas egyenesekkel. Az adatstruktura epitese
rendezesekkel O(n2 log n) idoben;
rendezesek nelkul O(n2) idöben (,,új egyenes lemmája").

3. gyakorlat (szept 26.) feladatai (gzipped PS, 21K)

4. eloadas (okt 2.)

Konvex helyzetu ponthalmaz dualisa: ,,homokora".
az eelek szamozasa (dinamikus programozas);
max. homokora keresese O(n2) tarral O(n3) idöben.
Konvex burok fogalma. Sikbeli konvex burok keresese:
egyenkenti hozzavetellel O(n log n) idoben;
,,csomagkotozo" algoritmussal O(kn) idoben;
,,oszd meg es uralkodj" modszerrel O(n log n) idoben.
Terbeli konvex burok keresesere is van O(n log n) ideju algoritmus.
Mese: ,,oszd meg es uralkodj"; ezen belul ,,3D ,,csomagkotozes".

4. gyakorlat (okt 3.) feladatai (gzipped PS, 22K)

5. eloadas (okt 9.)

Also becslesek konvex burok keresesere.
,,Kis"- es ,,nagy" Ben-Or tetelek.

5. gyakorlat (okt 10.) feladatai (gzipped PS, 24K)

6. eloadas (okt 16.)

Chen ,,output-erzekeny" algoritmusa konvex burok keresesere.
Also becslesek tobbdimenzios konvex burok keresesere.
A momentum-gorbe

6. gyakorlat (okt 17.) feladatai (gzipped PS, 20K)

7. eloadas (okt 23.) elmaradt

7. gyakorlat (okt 24.) feladatai (gzipped PS, 24K)

8. eloadas (nov 6.)

Also becslesek tobbdimenzios konvex burok keresesere (folytatas).
A ,,ciklikus polieder": polieder sok ellel, lappal, ... , hiperlappal.
A ,,felso becsles tetel".
,,Majdnem optimalis" algoritmus tobbdimenzios konvex burok keresesere.

8. gyakorlat (nov 7.) feladatai (gzipped PS, 23K)

9. elöadás (nov. 13)

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

9. gyakorlat (nov 14.)

10. elöadás (nov. 20)

Monoton síkdarabolások (folyt).
Lapok számozása ,,alulról felfelé".
Pont helyének visszakeresése síkdarabolásban (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.

10. gyakorlat (nov 21.) feladatai (gzipped PS, 23K) + Voronoi diagramm és elemi tulajdonságai is voltak!

11. elöadás (nov. 27)

A síkbeli VD-keresés visszavezetése 3D konvex burokra. Algoritmus O(n log n) idöben.
Delaunay-háromszögelés (VD duálisa). Ekvivalens definíció (,,alap-lemma"). Algoritmus O(n log n) idöben.
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.

11. gyakorlat (nov 28.)

12. elöadás (dec. 4): KONZULTÁCIÓ.

12. gyakorlat (dec 5.) ZÁRTHELYI.

13. elöadás (dec. 11):

Delaunay-háromszögelés extremális tulajdonsága.
MESE: véletlen algoritmus O(n log n) várható idöben.
Egyszerü (de nem felt. konvex) sokszög háromszögelései:
Mindig felbontható n-2 háromszögre;
Monoton sokszög n-2 háromszögre bontható O(n) idöben;
Tetsz. sokszög n-2 háromszögre bontható O(n logn) idöben;
Kamerák a képtárban.
[n/3] mindig elég (lemma!); kevesebb nem mindig.
Algoritmus [n/3] kamera elhelyezésére.
A minimum keresése NP-nehéz!

12. gyakorlat (dec 12.)


György Elekes
Last modified: Mon Dec 11 17:27:55 CET 2006