1. elöadás (szept 11.)

Sylvester sejtés - Gallai tétel

Parabolikus dualitás, duális Gallai

Ramsey tétele (véges gráfokra)

Erdös alsó becslése

1. gyakorlat (szept 11.) feladatai (gzipped PS, 20K) --- Sikgráfok is voltak!

2. elöadás (szept 18.)

Ramsey tétele halmazrendszerekre

A "happy end" probléma

Algoritmus nagy konvex sokszögek keresésére dinamikus programozással O(n³) tárral, O(n⁴) ido"ben.

Sikdarabolások adatstruktúrája: csúcsok, élek, lapok: rekordok --- plusz pointerek oda-vissza

Spec: sikdarabolás egyenesekkel. Az adatstruktúra épitése

rendezéssel O(n² log n) ido"ben;

rendezés nélkul O(n²) ido"ben (,,új egyenes lemmája").

2. gyakorlat (szept 18.) feladatai (gzipped PS, 25K)

3. elo"adás (szept 25.)

(folytatas) Új egyenes lemmájának bizonyitása

Konvex helyzetü ponthalmaz duálisa: ,,homokóra".

az élek számozása (dinamikus programozás);

max. homokóra keresése O(n²) tárral O(n³) ido"ben.

3. gyakorlat (szept 25.) feladatai (gzipped PS, 22K)

4. elo"adás (okt 2.)

Konvex burok fogalma. Sikbeli konvex burok keresése:

egyenkénti hozzávétellel O(n log n) ido"ben;

,,csomagkötözo''" algoritmussal O(kn) ido"ben;

,,oszd meg és uralkodj" módszerrel O(n log n) ido"ben.

Chen ,,output-érzékeny" algoritmusa konvex burok keresésére.

Térbeli konvex burok keresésére is van O(n log n) ideju'' algoritmus.

Mese: ,,oszd meg és uralkodj"; ezen belül ,,3D csomagkötözés".

4. gyakorlat (okt 2.) feladatai (gzipped PS, 23K)

5. elo"adás (okt 9.)

Alsó becslések konvex burok keresésére.

,,Kis"- és ,,nagy" Ben-Or tételek.

Alsó becslések többdimenziós konvex burok keresésére.

A momentum-görbe

A ,,ciklikus poliéder": poliéder sok éllel, lappal, ... , hiperlappal.

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

6. elo"adás (okt 16.)

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 tetszo"leges síkdarabolásban O(n) ido"ben.

Az igazi probléma: adott síkdarabolás ,,elo"-feldolgozása" úgy, hogy tetszo"leges pontról gyorsan [azaz o(n) ido"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 ido".

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é".

6. gyakorlat (okt 16.) nem volt új feladat

7. elo"adas (okt 23.) elmaradt

7. (pót)gyakorlat (okt 26.): kis-ZH feladatai (gzipped PS, 22K)

8. elo"adás (nov. 6)

Pont helyének visszakeresése síkdarabolásban (folyt).

Egy ötletes (de nem túl jó ideju") módszer: bináris keresés szeparáló élsorozatok között

Fokozatos javítás O(n) tárig és O(log n) ido"ig.

8. gyakorlat (nov 6.) feladatai (gzipped PS, 21K)

9. elo"adás (nov. 13)

A síkbeli VD-keresés visszavezetése 3D konvex burokra. Algoritmus O(n log n) ido"ben.

9. gyakorlat (nov 13.) feladatai (gzipped PS, 28K)

10. elo"adás (nov 20.)

Delaunay-háromszögelés (VD duálisa). Ekvivalens definíció (,,alap-lemma"). Algoritmus O(n log n) ido"ben.

A legközelebbi szomszédok gráfja. Algoritmus O(n log n) ido"ben.

Euklideszi minimális feszíto" fa O(n log n) ido"ben.

10. gyakorlat (nov 20.) feladatai (gzipped PS, 19K)

11. elo"adás (nov 27.)

Univerzális konvex fedések. Pál tétele (a ,,sonkásszendvics" módszer). A Borsuk--probléma.

11. gyakorlat (nov 27.) feladatai (gzipped PS, 22K)

12. elo"adás (dec 4.)

Egyszeru" (de nem feltétlenül konvex) sokszög mindig felbontható n-2 háromszögre.

Ha egy n csúcsú, e élu" G gráfban e>=4n, akkor metszési száma X(G)>=Ce³/n².

A síkban n pont és n egyenes között legfeljebb O(n^4/3) illeszkedés lehet -- és ez a nagyságrend el is érheto".

Az elo"zo" felso" becslés pontokra és egységkörökre is igaz -- de még n^1+epsilon -os alsó becslés sem ismert.

A sík n pontja között az egységtávolságok száma O(n^4/3).