tematika: kimaradt: kd fa range search-re - n tar, nlog n ep, gyok n+k ido range tree - nlog n tar, log^2 n +k ido fractional cascading - log n +k ido tizenharmadik ora: all. osszes alg kozbeni haromszogre koreirt koreben levo pontok osszegenek varhato erteke O(nlog n) biz. leszamoljuk q\in i. korben keletkezett haromszog koreirt kor incidenciak varhato erteket es szummazzuk. ha q az i+1. pont, akkor a korabban keletkezett haromszogekre ez a q foka-2 lenne. NEM, mert mar nincs minden haromszog az abraban!!! jo biz??? minden haromszogre 3/i az eselye, hogy az i. korben keletkezett, tehat ez konst/i. szummazas utan tehat nlog n-et kapunk. alk: min feszfa siktavokra szamithato nlog n-ben, mert resze D-graf (noveljuk koroket kul kompok pontjaibol). RND alg konvex burokra terben: csucsokat veletlen sorrendben vesszuk taroljuk, hogy melyik meg nem vett csucs melyik lapokat latja horizonton vegig tudunk setalni es uj lapokat beilleszteni, updateelni lathatosagot - okosan alg alatti lapok varhato erteke O(n) euler miatt lathatosag updateelesnel ossze kell adni, hogy hany horizont el lathathato hany pontbol ezt felulbecsuljuk a "flap"-ok lathatosaganak szamaval (ez ket haromszog, kozos ellel, a kozoset kell latni) egy q varhatoan q fok flapot lat es ezekbol konst/i keletkezett i. korben tehat mint delaunaynal, nlog n-t kapunk. mj. ezt lehet altalanositani d-dimre, opt lesz: n^[d/2]+nlog n-es dualis: konvex burok teteje <-> sikok also burkoloja dualis kapcsolata sikbeli V-diaggal: egysegparaboloid es z=0 sikbeli pontokbol erintosikjai tizenkettedik ora: mj. ha szogek helyett hosszakat akarnank minimalizalni, az NP-teljes D-haromszogeles kiszamitasa - lehetne V-diagbol is, de helyette RND hozzaadunk ket tavoli pontot, hogy haromszogbol induljunk, ezzekkel nem foglalkozunk veletlen sorrendben hozzaadjuk pontokat es javitjuk rossz eleket uj pont elei mindig jok, vele szemkoztiek romolhatnak csak el kesobb uj szemkoztiek is, de ez osszesen konst RND sorrend miatt haromszogeket faszerkezetben taroljuk, levelek aktualisak, belsok mar kitoroltek varhatoan O(n) haromszog keletkezik folyamat kozben, mert lepesenkent fokszamnyi amikor uj pontot beszurunk, annak a helyenek a megkeresese mennyi? max azokon kell vegigmenni, akik tartalmazzak (mindnek 2-3 gyereke, azok kozul nem gond valasztani) csuszas 13.-ra! konvex burok magasabb dimben also korlat d dimben: n^[d/2], mert mar bonyolultsag is ennyi momentum gorbevel ha csak mind konvex burkon van-e a kerdes, akkor mindre megnezzuk, hogy kiadja-e tobbi konvex kombinacioja, ez n db nxn-es egyenletrendszer, szoval poly. viszont pl azt eldonteni, hogy minden arc szimplex-e es hasonlo problemakra n^[(d-1)/2] ismert (hipsik kerdesekre), lasd http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/convex.pdf mj: van n^[d/2]+nlog n-es algoritmus ami megadja konvex burkot 3d-ben ez nlog n. itt bonyolultsag lin euler-formula miatt mj: ezt kombinalva channel nlog h-sat kapunk. sikdarabolas mintajara lehet terdarabolast is tarolni tizenegyedik ora: farthest-point V-diag kiszamitasa rnd alg: kiszam burok, rnd sorrendben elhagyjuk pontjait, csak ket szomszed koze kerul uj uj hatarahoz sorban vesszuk regi eleket, hogy mit metsz, ha k lesz, akkor max O(k)-t kell nezni tehat burokkereses + O(n) rnd ido alk: smallest width annulus: 3 fajta, hogy belso/kulso koren hany pont, ket V-diagot kell osszemetszeni, sot, helyette csak eleket paronkent, n^2 ido domborzati terkep - pontokon linearisan kozelitjuk haromszog csucsaibol - de hogy haromszogeljunk? konvex negyszognek melyik ele rossz - szemkoztiek osszege vs 180, max szog min, min szog max amiben nincs rossz el, az jo - egyedi? alt helyzetben? Delaunay haromszogeles - V-diag hataros lapjait osszekotjuk szakaszokkal sikgraf, mert p1p2 a kozos ures korukon belul megy, meg p3p4 is, vmelyik szemkozti osszege nagyobb 180 p1p2p3 haromszog, ha korbeirt koruk ures es p1p2 el, ha van kozos ures koruk (ami zart, ha nem alt helyzet) ami jo haromszogeles, az D-haromszogeles, mert ha nem, vegyuk pi-t, ami p1p2p3-ban es p1pip2 max es ellentmondas tizedik ora: V-diag kiszamitasa alg 1: cellankent nlogn, ossz n^2logn alg 2: sopressel, Fortune's alg nlog n ido (optimalis) sopreskor taroljuk parabolat, amik feletti reszrol mar tudjuk, hogy melyik cellaban van parabolak talalkozasai az eleken mennek, talalk eltunese ad uj csucsot uj parabola csak uj ponttal keletkezhet (esetek), ezek es eltunes az eventek (eltunes neha teves, max 2 uj pontonkent) mj. ez hasonloan megy, ha szakaszok vagy mas egyszeru dolgok vor-at szamoljuk alk. kor alaku robot hova tud menni farthest-point V-diag: itt csak a konvex burok szamit, lapok vegtelenek kilencedik ora: irjuk le legalsok szamat, davenport-schinzel sorozatok lambda1=n (egyenes), lambda2=2n-1 (parabola), lambda3=theta(n\alpha(n)) also burkolo meghatarozasa, ha s-szer metszik egymast (parcra s+2) alg 1: sopressel: C_s n^2log n (esetleg log n elhagyhato) alg 2: oszd meg es uralkodj: \lambda_s(n)log n ido melyik a legkozeleppi bolt? voronoi-diagramm, -cella, -graf ha nem minden egy egyenesen, grafban szakaszok es felegyenesek, csucson ati minden felsikba megy el, of a graf euler formula, csucs,el<=>ures koren hatarolo fovarosok nyolcadik ora: crossing lemma - tippelgessuk opt lerajzolast K_n-re meg crossing lemmat dey: pl fokok, max n curve halving segmentsbol, csucson at egyik felsikban sincs ketto metszespont<=erintok<=n \choose 2 es crossing lemma-val kesz http://compgeom.cs.uiuc.edu/~jeffe/open/half.html hetedik ora: diszkrepancia, szamitasa ha van n pont negyzetben es felsikokra mind hataran 1 vagy 2 pont, elobbiekre n x n ido, utobbiakra dualitas es sikdarab egyenesekre arra minden csucsra egyszerre kiszamoljuk, kesz hany pont van a k. szinten? k-level dualisa k-set Omega(n^(c (logk)^{1/2})) geza and O(nk^{3/2}) dey viszont <=k-setre nk a maximum, ha k 2ax-b, tartja a "pont az egyenes felett van"-t az y=x^2 parabola pontjai erintokbe, tobbiek felettuk/alattuk levo parabolapont szerint diszkrepancia defje otodik ora: sikdarabolas szamolasa egyenesekre n^2 idoben uj egyenes lemmaja: uj egyenes altal elmetszett lapok osszoldalszama <8n ha uj vizszintes, akkor van ket legfelso, ket legalso, tobbibol meg minden regin max 1 ontes: csak poligonokat nezunk, ezek egy iranyban kihuzhatoak, nem ugy, mint csavar vagy felkor eloszor 2d, aztan 3d tehat feladat: felsikok egy metszespontjanak kiszamitasa (-szor n ido) alg 0: elozo modszerrel n^2 ido alg 1: felezes es kozos finomitasszamolas - T(n)=O(nlog n)+2T(n/2), ez nlog^2 n alg 2: kozos finomitas konvexekre megy lin idoben, amibol osszido nlog n mj: ennel nem is lehet gyorsabban egesz metszet, mert ez olyan konvex burok dualisa-szeru alg 3: LP-vel legmagasabb csucs, ez n^2 ido, mert n-szer kellhet hivni 1-dim algot alg 4: RND LP: eselye, hogy csucs szomszedjat vettuk 2/i es igy O(n) varhato ido negyedik ora: haromszogeles monoton poligonra hogyan dontsuk el, hogy adott sikdarabolas melyik lapjan van egy pont? elotte: hogyan dontsuk el, hogy melyik ket szam kozott van egy uj szam? alg 1: minddel osszevetni n ido alg 2: tablazat minden pontrol sok tizedesjegyik, exp tar es ep, kereses 1 ido alg 3: sorbarendezzuk pontokat, nlog n ep, n tar, log n ido eloszor monotonna tesszuk sikdarabolast, definialhatjuk az alatta van relaciot ez kormentes, mert n=2-re nincs kor es nagyobb n-ekre meg indukcio, legjobb legbal ponton atmeno egyenessel beszamozzuk a lapokat, definialjuk az Sk szinteket - minden csucsbol megy balra es jobbra is el (kiveve legszelsoket) ilyet lehet csinalni nlog n idoben barmely sikdarabolasbol balra jobbra sopressel: minden savban taroljuk utolso pontot is poligonon kivuli reszeket ignoraljuk az y-monotonositasnal ezutan a haromszogeles (hf): also es felso burkolobelieket x-koord szerint vesszuk es esetek errol minden: http://maven.smith.edu/~orourke/books/ArtGalleryTheorems/art.html masodik ora: ismetles, milyen algoritmusok voltak elozo oran hogyan szamoljuk ki n db egysegkor konvex burkat? (konvex burok+egysegkor) also korlat 2 dim konvexre: Yao, Ben-or: annak eldontese, hogy mind az n pont konvex burkon-e is \Omega(nlogn) elotte: n szam mind kulonboze-e eldontese is \Theta(nlogn) biz: 1, ha kerdesek csak linearisak - R^n konvex reszhalmaza, of is, de n! ilyen van 2, ha d fokuakat kerdezunk, akkor Thom-Milnor theorem: az of komponensek szama \le d(2d-1)^{n+h-1} ahol h a polinomok szama, kesz ha n pont konvex burkon, azok is (n-1)! sorrendben lehetnek rendtipus definicioja szakaszok metszespontjainak kiszamolasa - (n+h)log n idoben fontrol soprunk vizszintes egyenessel taroljuk pontokat sorban: Q keresofa es aktualis szakaszokat: T keresofa kiegyensulyozott binaris keresofaban beszuras, torles meg minden megy log meret = log n idoben more: http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm elso ora: mit tud eldonteni a szemunk? haromszogben van-e pont, komplikalt konkav sokszogben van-e (felegyenes pontbol) bevezetés adatstruktúrákba: tömbök, láncolt listák tobbnyire nem reszletezzuk, de neha szukseg lesz vmi trukkosebbre szimbolikus perturbacio konvex burok trivi: minden ir. elhez megnezzuk, hogy hataron-e - n^3 ido csomagkotozo (Jarvis march): also es felso burkot kulon keressuk, novekvo x-koord szerint - hn ido pontok egyenkent: ha mar rendezve vannak pontok x-koord szerint, akkor n ido - "amortizacios" ido divide et impera: ez is n ido, szamolas uugy, mint elobb - ind: O(n) - h ido Chan output erzekeny alg: nlog h ido, more: http://en.wikipedia.org/wiki/Chan%27s_algorithm