Matematika | Felsőoktatás » Tóth Csaba - Illeszkedési problémák az Euklideszi térben

Etvs Lornd Tudomnyegyetem Termszettudomnyi kar matematikus szak Illeszkedsi problmk az euklideszi trben DIPLOMAMUNKA Ksztette: Tth Csaba Tmavezet: Szab Lszl 1997. Tartalom: Jellsek Bevezets 1. A Szemerdi-Trotter ttel 2. 3. 5. 6. 9. 12. 15. 24. 30. 30. 33. 44. 49. 50. 50. :::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::: 1.a Bizonyts metszsi szmokkal 1.b Egysgtvolsg problmk 1.c Als becsls :::::::::::::::::::::: :::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::: 2. Kvetkezmnyek 3. Kombinatorikus grbk 4. Tbb dimenzi s ltal nos t sok :::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::: 4.a Kifesztett skok 4.b Megszortsok az an alterekre 4.c Egy cellban lv pontok :::::::::::::::::::: ::::::::::::::::::::::::::::::::::: ttekints Ksznetnyilv n t s Irodalomjegyzk :::::::::::::::::::: ::::::::::::::::::::::::::

::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::: 1 Jellsek: a b] = fn 2 N : a  n  bg, M X ] = az X valszn sgi vltoz vrhat rtke, (G E ) grf, melynek cscshalmaza G, lhalmaza E , P lesz ltalban egy n elem ponthalmaz Rd -ben, E egy e elem rszhalmaza P (Rd ) hatvnyhalmaznak, et = fs 2 E : js Pj  tg. Ha x 2 Rd s f g : Rd ! R, akkor g(x) = O(f (x)) esetn fg xx ltezik s korltos, () () g(x) = o(f (x)) esetn fg xx ! 0, mg kxk1 ! 1 () () g(x) = (f (x)) esetn fg xx ltezik s korltos. () () 2 Bevezets E dolgozat clja, hogy ttekintst adjon a Szemerdi-Trotter ttel eddig ismert alkalmazsi terleteirl s ltalnostsairl. A kombinatorikus geometrinak ez az alapvet ttele aszimptotikusan les becslst ad az euklideszi sk n pontja s e egyenese kzt fellp illeszkedsek maximumra n e fggvnyban: I = O(np= e = + n + e). Vagy ezzel ekvivalens mdon2

(lsd az 12 ttelt) t 2 2; C n] esetn a t pont egyenesek szma et = O( nt3 ). A trivilis becsls et-re n = O(n ). De a pontok s egyenesek kombinatorikus tulajdonsgaibl ;n ;t 2 n levezethet O( t2 ), ugyanis az lehetsges pontprbl legalbb esik egy mi;n ; t  2 n nimum t pont egyenesre, ezrt et  = = O( t2 ). Ez a becsls les is a vges geometrik esetben, ahol n = e = k + k +1 s ek = n(k +1) = e(k +1) = O( nk22 ). A problmakr els ttrse Beck Jzsef melyben megp 1982-es ttele volt, 2 n mutatta, hogy euklideszi skon t 2 2 C n] esetn et = O( t2 05 ) s ezzel egy kombinatorikus lltssal tett klnbsget az euklideszi s a vges projektv geometrik kztt. Mg ugyanebben az vben Szemerdi s Trotter javtott ezen a becslsen. Az  eredmnyk lesnek bizonyult, azonban az azta vizsglt ms illeszkedsi problmkra mr csak nhny esetben ismert a pontos aszimptotika. 1995-ben Szkely Lszl tallt egy elegns bizonytst a Szemerdi-Trotter ttelre extremlis

topolgikus grfelmlet felhasznlsval. A Szkely fle bizonyts tletre alapozva Pach Jnos s Micha Sharir adott fels becslst skbeli pontok s grbk illeszkedsi szmra. A grbkre csak kombinatorikus megszortsokat tettek gy, mint: k adott pontra legfeljebb s grbe illeszkedhet s kt grbe legfeljebb s pontban metszi egymst. gy pldul k = 3 s = 1 konstans paramterekkel n pont ill. e kr illeszkedseire rvnyes korlt I = O(n = e = + + n + e). Ugyanez a kombinatorikus tulajdonsg jellemzi a hromdimenzis euklideszi tr skjait is, ha kiktjk, hogy semelyik hrom adott pont ne legyen kollineris. Ezzel a felttellel Edelsbrunner, Guibas, Sharir tallt 1990-ben az elznl alig gyengbb fels korltot a pontok s skok illeszkedsre: I = O(n = ; e =  + + n + e) tetszlegesen kicsi pozitv -ra. Ennek a korltnak a bizonytsa egy rekurzv eljrson alapul s hasznlja K.L Clarkson 1987-es vletlen mdszeres eredmnyeit. A tetszleges dimenziban rvnyes fels

korlt pontok s hiperskok illeszkedseinek szmra a Szemerdi-Trotter ttelbl vezethet le indukcival, de mg ennl is gyengbb eredmnyt ad. Az ismert legjobb als korlttl mindkett messze van. Ms megkzeltsban a Szemerdi-Trotter ttel hromdimenzis ltalnostsnak tekinthetjk azt a pontokra s skokra vonatkoz illeszkedsi problmt, ahol a skokrl csak annyit tesznk fel, hogy tertalmaznak hrom an fggetlen adott pontot. Erre Clarkson, Edelsbrunner, Guibas, Sharir s Haussler eredmnyei nyomn mr ismert a (log faktortl eltekintve) pontos aszimptotika 2 3 2 3 2 2 2 2 2 2 2 : 3 5 4 5 3 5 3 4 5+2 Ki fog derlni, hogy az illeszkedsi problmk s eredmnyek szoros kapcsolatban llnak msik kt rgi problemakrrel: az n. egysgtvolsg problmval s az elrendezsek komplexitsval. Az egysgtvolsg problmnak tbb vltozatra az eddig ismert legjobb eredmny illeszkedsi szmokra adott fels becslsekbl szrmazik Mg e hipersk elrendezsben n

cella komplexitsra sok esetben fellrl becsli e hipersk s n pont illeszkedseinek szmt. A felhasznlt mdszerek a kombinatoriai, geometriai ismeretek mellett vletlen mdszerekre, algoritmusok bonyolultsgra s a topolgia elemeire is tmaszkodnak. 4 1. A Szemerdi-Trotter ttel Szemerdi Endre s W.TTrotter 1982-ben bizonytotta a kvetkezt 1.1 Ttel: Legyen adott R2 -ben n klnbz pont s e klnbz egyenes Ekkor a pont-egyenes illeszkedsek szma I = C (n = e = + n + e), (C > 0). 2 3 2 3 2 A ttel tfogalmazsai is Szemerdi-Trotter ttelknt ismertek, ezrt mi is gy fogunk rjuk hivatkozni. Itt beltjuk ezek ekvivalencijt 1.2 llts: Legyen adott R2 -ben n pont s e egyenes Ekkor az illeszked- sek I szmra egyszerre teljesl (1) I = O(n = e = + n + e) (2) p 2 3 2 3 n  e  n eseten I = O(n = e = ) 2  2 3 2 3  (3) et = O nt + nt  ha t 2 2 n] ahol et jelli a legalbb t pont egyenesek szmt. 2 3 p Bizonyts: (1) ) (2): n  e  n2

esetn n = n2=3n1=3  n2=3e2=3 s e=e = e = e = n = . 2 3 1 3 2 3 2 3  p n2 t3  (2) ) (3): Elszr azt ltjuk be, hogy 2  t  D n esetn et = O , p = = (D > 1). Legyen C > 0 olyan, hogy n  e  n esetn I < Cn e teljesljn. Indirekte tegyk fel hogy tallhat e = C D n =t darab legalbb 2 n t pont egyenes. Ezekpilleszkedseinek szma I  et = C D t2 . Msrszt p t 2 CD C n] esetn n  e  n s (2)-bl I  Cn =; e = = C D n =t kvetkezik, ellentmonds. t 2 2 CD ; 1] esetn pedig et  n = O nt32 p ;  Most azt ltjuk be, hogy t 2 2n + 1 n] esetn et = O nt . Tekintsk az sszes legalbb t pont egyenest. Az els k darab egyenes (k 2 1 et]) legalbb t +(t ; 1)+(t ; 2)+ +(t ; j +1) adott pontot fed le, hiszen indukcival a k-adik maximum k ; 1 adott pontban metsz kisebb index egyeneseket s a szummba p 2 nem kerlhetnek negatv tagok, mert t + (t ; 1) + + 2 + 1 = t t; > n = n. gy az et egyenes ltal lefedett sszes pontra: n  t + (t ; 1) + + (t ; et +

1) > > tet=2, ahonnan et < 2n=t. 2 3 2 3 2 3 3 2 3 3 2 3 2 3 2 3 3 2 2 ( 1) 2 5 2 2 2 2 (3) ) (1). Tudjuk, hogy t 2 2 Dpn] esetn et  C nt32 Becsljk fellrl az illeszkedsek szmt Legyen l a legkisebb olyan p termszetes szm, hogy = Cn =l  e: Ekkor l  8(Cn =e) A legfeljebb D n pont egyenesek. sszes illeszkedseit fellrl becsli pn  = Z D pn DX n n 1 dt = e + el + C t  e + e8 C e + Cn t 2 3 2 1 3 2 t=l 1 3 2 2 3 ; 2=3 2=3 C  l  3 = e + O n e 2 n l1 ; D1 n  e + O(n = e = ): p p egyenesek szma legfeljebb DC3 n. Illeszkedjen az A D n-nl tbb pont p 0 egyes P egyenesekre a(i)  D n pont. Ezen egyenesek sszes illeszkedse I = = i a(i). Ha egyenknt rakjuk le az egyeneseket a skra, akkor a j -edik legalbb a(j ) ; (j ; 1) jabb pontot fed le, mert az els (j ; 1)-gyel legfeljebb j ; 1 P P P 3 pn P metszspontja van. n  i(a(i) ; (i ; 1))  i a(i) ; i (i ; 1)  i a(i) ; ; O(n). Ebbl I 0 = O(n) 2 2 3 2 3 2 2 C D =1

2 1.a Bizony t s metszsi sz mokkal A Szemerdi-Trotter ttel eredeti bizonytsa hosszadalmas s a konstans faktor is C = 10 . Azta tbb rvidebb bizonyts is szletett (Pl lsd 11]-t) Minden fels becslst bizonyt ttel alapja egy az euklideszi tr elvlasztsait jellemz segdttel s egy statisztikus becsls. Szkely Lszl 1995-s bizonytsa 27] a geometriai grfok metszsi szmnak als becslsre pl, ami csak az Euler-fle poliderttelt sp a Jensen-egyenltlensget hasznlja. Eszerint az 11 ttelbeli konstans faktor 3 100. Szkely Lszl bizonytshoz clszer bevezetni nhny egyszer fogalmat. 60 1.4 Definci : Geometriai grf: (G E ) egyszer 1 absztrakt grf s annak f : (G E ) ! (R  P (R )) skbagyazsa gy, hogy semelyik kt grfpont kpe nem esik egybe, az lek kpei pedig a pontokat sszekt folytonos nylt grbk, s kt l kpeinek metszete vges halmaz. 2 2 1.5 Definci : Egy geometriai grf metszsi szma az sszes lpr metszsszmnak az sszege,

azaz X jf (i) f (j )j: ij 2E 1 hurokl s tbbszrs l nlkli 6 Jelljk ezt a szmot cr(G E )f -fel vagy cr(G)-vel az angol crossing szbl. 1.6 Definci : Egy absztrakt egyszer grf metszsi szma a minimlis metszsi szm skbarajzolsnak metszsi szma: cr(G E ) = minf fcr(G E )f : (G E )f geometriai graf g Euler poliderttele alapjn 1.7a Ttel: (G E ) geometriai grfban ha jGj = n, jE j = l s l > 3n ; 6, akkor cr(G E )  1: 2 Ennl azonban adhat jobb becsls is, ha l  4n. Egymstl fggetlenl bizonytotta Leighton 21] valamint Ajtai, Chvtal, Newborn, Szemerdi 2] a kvetkez ttelt, de mr Erds s Guy is ilyen aszimptotikt sejtett 17]. 1.7b Ttel: Ha (G E ) geometriai grf, jGj = n jE j = l l > 4n, akkor 1 l : cr(G E )  100 n 3 2 Bizonyts: Indukcival azt bizonytjuk, hogy   3 n l : cr(G E )  64 4 ;n 3 3 2 ;  Ebbl mr addik a ttel lltsa. Elszr is n  9 esetn l  n miatt l   4n csak akkor teljeslhet, ha n =

9 l = 36 s (G E ) teljes grf. Erre igaz a egyenltlensg. 2 7 10  n s 4n  l  5n esetn az egyenltlensg jobb oldala legfeljebb l ; 3n, 3n 3 3 n ; l l mert fellrl becslhet n2 ;n 3 =  n2 -vel. S az l = n helyettestssel, az  ! ( ; 3) ; (=4) harmadfok fggvnynek a (4 5) intervallumban nincs zrushelye,  = 5-ben pozitv. Ha l > 5n, akkor ksztsk el (G E ) grfhoz s v 2 G cscshoz a Gv grfot gy, hogy (G E )-bl kitrljk v-t s a r illeszked leket. Ezzel a grf egy metszst 4-szer trljk ki, sszegezve minden v 2 G-re: 3 ( 64 3 1) 4! ( ) 8 64 (n ; 4)cr(G E ) = X v2G cr(Gv  Ev ): Mivel v-vel egytt legfeljebb n ; 1 lt tudunk kitrlni, Gv lszmra s cscsszmra teljesl az indukcis felttel, gy Gv -re alkalmazhat a ttel: ;n;  X X 3 lv = cr(Gv  Ev )  64 ;n;  v2G v2G 1 3 4 1 3 2    3 n ;l  n ; 4 n = 64 4 n n n;2 A kvnt egyelnsghez az kell, hogy 3 3 P v2G lv : l 2  n 3 n;2  3 1 X lv n v2G l P 3

1 ;1 P teljesljn. A Jensen egyenltlensgbl n v2G lv  n = nl ; 2l, mert minden lt ktszer hagytunk el. Teht 1  3 n n;2  3 1 X lv n v2G l   n n;2 3 3 3  v2G lv 1 1 Xl l n v2G v 3 3 !3 . Itt P v2G lv = = 1: 2 Ennek segtsgvel mr knnyen bizonythat a Szemerdi-Trotter ttel: Bizonyts (1.1 Szemerdi-Trotter ttel): Hagyjuk el azokat az egyeneseket, melyekre nem illeszkedik pont. Elg a ttelt erre a rendszerre bizonytani, hiszen az illeszkedsek szma ezzel nem vltozik, C (n = e = + n + e) pedig nem n. Ksztsnk egy (G E ) grfot gy, hogy G az adott pontok halmaza, E ben kt grfpontot akkor kt ssze l, ha egy adott egyenesre illeszkednek s ezen az egyenesen nincs kzttk ms adott pont. A grfnak ;  metszse csak kt adott egyenes metszspontjban lehet. gy cr(G E )  e < e . 2 3 2 3 2 2 8 Az egy egyenesre illeszked pontok szma eggyel tbb az egyenesen lv grflek szmnl. Teht a pont-egyenes illeszkedsek

szma: I = l + e A 16 ttel szerint: ha I ; e  4n, akkor 1 (I ; e)  cr(G E ) < e  ahonnan I  5(ne) = + e: 100 n Azaz tetszzleges I -re I  5(n = e = + e + n). 3 2 2 3 2 2 3 2 3 2 1.8 Megjegyzs: Vegyk szre, hogy az euklideszi sk egyeneseinek tulajdonsgi kzl csak annyit hasznltunk ki, hogy ; kt egyenes egy pontban metszi egymst, (cr(G E )  e ) kt pontra legfeljebb egy egyenes illeszkedik, (Euler T.) az egyenes egyszer 2 grbe (darabjai grflek skbarajzolsai), az egyenes nylt grbe (egyenesen tbb pont van, mint grfl), az egyenes kt flskra vgja a skot (Euler-ttel). Az ezeket kielgt grbeosztlyra vltoztats nlkl igaz a ttel. Az els kt felttel arra cserlhet, hogy brmely kt grbe legfeljebb K 2 N pontban metszi egymst. Ekkor az illeszkedsek szma I  5K = (n = e = + n + e) Ha zrt grbket is megengednk, mdostani kell a bizonytst. A legalbb kt pontot tartalmaz grbk minden szomszdos pontpr kztti szakaszt tekintsk

grflnek. Az egypont grbket eltrljk Ezzel legfeljebb e darab illeszkedst hagyunk el. gy l  I  l + e I  5(n = e = + e) vagy I  4n + + e. Figyelembe vve az elhagyott grbk illeszkedseit is mindkt esetben I   5(n = e = + 4n + 2e) + e  5(n = e = + e + n) 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 1.b Egysgt vols g problm k Itt clszer megemlteni egy, az egysgtvolsg problmra adott becslst. Pontosabban igaz a 1.9 Ttel: Adott n klnbz pont R2 -ben Jellje d(n) az egymstl egysgtvolsgra lv pontprok szmt. Ekkor d(n) = O(n = ) 4 3 2 nmetszs nlkli 9 A ttelt elszr Spencer, Szemerdi s Trotter bizonytottk 28] a SzemerdiTrotter ttelbl, az itt kvetkez bizonytsban szerplnl sokkal rosszabb konstansfaktorral. Szkely bizonytsval ez mr a metszsi szmok becslsbl is kvetkezik. Bizonyts: Tekintsk az n klnbz pontot s a krjk rt egysgsugar krket. A krk olyan zrt grbk, hogy brmely kett legfeljebb kt pontban

metszi egymst s brmely kt pontra legfeljebb kett illeszkedik. A rendszerben az illeszkedsek szmra igaz I  8(n = n = + 4n + 3n)  15n = : 2 3 2 3 4 3 Az illeszkedsek szma pedig ppen a fellp egysgtvolsgok ktszerest adja. 2 Hasznos lesz az Ajtai, Chvtal, Newborn, Szemerdi Leighton fle metszsi szm becsls egy ltalnostsa a tbbszrs l geometriai grfokra. Ezekre a metszsi szm analg mdon de nilhat. Szintn Szkely Lszl bizonytotta az albbi les eredmnyt. 1.10 Ttel: Legyen (G E ) egy tbbszrs l geometriai grf Minden l legfeljebb K -szoros. jGj = n jE j = e e  5nK Ekkor  cr(G E ) =  e : nK 3 2 Bizonyts: Az E lhalmazt diszjunkt darabokra vgjuk:  E= i20log2 K ] Ei : Ei-ben azok az lek szerepelnek, amelyek multiplicitsa 2i 2i ]-ba esik. Jellje Ei azt az lhalmazt, melyben Ei tbbszrs leit egy l helyettesti. A (G Ei) grfok kztt megklnbztetnk ritkkat s s r ket. (G Ei) s r , ha jEij > > 2 2i n

(i 2 0 log K ]), egybknt ritka. A ritka lhalmazokra teljesl az, hogy P E ritka jEi j  4Kn. Msrszt X X e jEi j  e ; jEi j  e ; 4Kn  : 5 E sr E ritka +1 2 i i i Segdttel: Ha egy (G E ) absztrakt grfban minden l K -szoros, akkor a   (G E ) egyszeres l grfban cr(G E ) = cr(G E )=K . 2 10 Bizonyts: Vegyk a (G E ) grf egy skbarajzolst cr(G E ) metszssel. Szorosan minden l mell rajzoljunk mg K ; 1 lt. Ez (G E ) skbarajzolsa K cr(G E ) metszssel. Megfordtva, nzzk (G E ) egy skbarajzolst. Minden prhuzamos lbl vlasszunk ki egyet. Ezt megtehetjk K jEj-flekpp Ezek mindegyike legalbb cr(G E ) metszst ad. s minden metsz pr K jEj; -szr llt el 2 Eszerint: 2K 2K X X X jEi j cr(G E )  cr(G Ei )  2 icr(G Ei)  i  100 n 2 i i E sr 2 2 log log 3 2 2 2 =0 =0 i X  jE  j 3 jEi j3 1 i  =  i 2 2 i= 3 1002 n 100 n 2 E sr E sr X i i a Hlder egyenltlensg szerint cr(G E )  1001n  2 X jE  j i

2i=3 !3  = E sr 2 i=3 i X (2i= ) = !2 3 2 3 E sr i  1=100 e : Kn 3 2 2 A ttelt egy ksbbi fejezetben felhasznljuk, de emellett van kzvetlen alkalmazsa ismt a skbeli pontok ltal maeghatrozott tvolsgok krbl. Erds 18] egy 1946-os sejtse szerint p n pont a skban legalbb (n= log n) klnbz tvolsgot hatroz meg  n-et mutatott meg. Tbb kisebb-nagyobb elrelps utn Chung, Szemerdi s Trotter 4] mutatott 1992-ben n = =(log n)c klnbz tvolsgot. Az egy pontbl indul klnbz tvolsgok szmra 1990-ben a legjobb eredmny cn = volt Clarkson, Edelsbrunner, Guibas, Sharir, Welzl 7] cikkben. A tbbszrs l grfok metszsi szmnak als becslsbl egyszer en kvetkezik Szkely Lszl 31] albbi ttele. 4 5 2 3 1.11 Ttel: Legyen adott n klnbz pont R2-ben Ekkor kivlaszthat a pontok egyike, hogy az abbl mrt klnbz tvolsgok szma (n = ). 4 5 Bizonyts: Legyen t az egy pontbl mrt klnbz tvolsgok maximuma. Feltehet,

hogy t = o(n= log n), klnben kszen lennnk. Minden pont kr rjunk krt az ott fellp tvolsgoknak meegfelel hosszsg sugarakkal Ksztsnk egy geometriai grfot, melynek az n pont a cscshalmaza, lei pedig azon krvek szomszdos pontokat sszekt darabjai, melyeken legalbb 3 pont van. Az gy kapott grf leinek szma legalbb cn , de lei nem felttlen korltos multiplicitsak. 2 11 Ha a p q grfl multiplicitsa k, akkor a pq szakasz felezmerlegesn van legalbb k krkzppont. Ha egy egyenesen k adott pont van, legfeljebb 2kt krvnek lehet felezmerlegese. gy a legalbb K multiplicits lek szma: pn n n X X X e i2it = 2t ei + 2t ei p i K i K i n = = = = +1 ahol e i jelli a pontosan i pont egyenesek szmt. A Szemerdi-Trotter ttelbl pn pn Z pn X X ei  Cn =i  Cn 1=t dt = O(n )=K : K; i K i K Pn Az 1.2 llts (3) ) (1) bizonytsban lttuk, hogy i pn ei = O(n): p Ha elhagyunk minden legalbb K = L t-szeres lt, ahol L elg nagy konstans p

akkor ezzel 2Ct(n =(L t)+ L tn)  (c=2)n -nl kevesebb lt hagyunk el, gy mg marad (n ) l a grfban. Erre alkalmazva az 1.10 ltalnostott metszsszm-ttelt   cn n 0 cr(G E )  p = p : nL t t Ugyanakkor legfeljebb nt krt rajzoltunk s 2n t metszst kaphatunk. Ebbl t = (n = ). = 2 = 3 2 3 2 = = 2 2 1 +1 2 2 2 6 4 2 2 2 4 5 2 1.c Als becsls A Szemerdi-Trotter ttelbeli fels becsls aszimptotikusan a legjobbnak bizonyult, ugyanis adott e n-re tallhat n pont s e egyenes R -ban (n = e = +n+e) illeszkedssel. Erdstl 1] szrmazik a kvetkez konstrukc 2 2 3 2 3 1.12 Ttel: Tallhat olyan c > 0, hogy brmely n e 2 N-hez van n klnbz pont s e klnbz egyenes, hogy a kztk ltrejv illeszkedsek szma legalbb c(n = e = + e + n). 2 3 2 3 Bizonyts: Az illeszkedsek szmt jelljk I -vel. Nyilvn I  max(n e), hiszen ezt elrhetjk, ha az sszes pont kollineris vagy az sszes egyenes konkurrens. = = Arra kell konstrukcit tallnunk,

hogy p I  =cn e valamely c-re. Legyen n helyett n~ 2 (1=20n n) olyan, hogy 2j n~ s n~ 2 N, (ilyen van, ha n  20), e helyett e~ 2 (1=5e e) pedig olyan, hogy e~ = 2 N igaz legyen. Teljesljn mg   cpe~ = = k 2 N (1) n~ 2 3 2 3 1 6 1 3 1 3 12 valamely ksbb meghatrozand c > 0 konstanssal. p A ponthalmazunk legyen P = f(i j ) : i j 2 1 n~ ]g r s 2 N olyan, hogy s  r r s 2 1 k] lnko(r s) = 1: Ekkor ( " Z rcs. Legyen 2 p #) Lrs := y = sr (x ; i) + j : i 2 1 r] j 2 1 2n~ jLrs j = r p n~  2 L3,1 azaz Lrs az psszes (i j )-t s (i + r j + s) pontot sszekt egyenes, ahol i 2 1 r], j 2 1 n ]. Vgl legyen L := Lrs rs 2 k  s < r ~ 2 1 ] lnko(r s) = 1  Mivel lnko(r s) = 1, a klnbz Lrs-be tartoz egyenesek meredeksge klnbz. i 2 1 r] miatt Lrs -ban megadott minden egyenes klnbz Ha ugyanis y ; j = rs (x ; i ) s y ; j = sr (x ; i ) kt Lrs-beli egyenes, akkor j ; j = rs (i ; i ) 2 Z, amibl j = j  i = i . gy az

L-ben megadott egyenesek mind klnbzek, ezrt: 1 1 2 1 1 2 2 1 2 2 1 2 p p k X n ~ (r)r n~  jLj = jLrs j = r 2 = 2 rs rs r X X =1 ahol (r) = jfs 2 1 r] : s rgj az Euler-fle fggvny. Az albbi kt, a fggvnyre vonatkoz becslst hasznljuk fel. Mindkt esetben (r) = r ; ; jfs 2 1 r] : sjrgj de ncit hasznljuk. - 13 k X (i)  i=1 k X j =1 k X (k ; kj ) = k ; k 1=j  k ; k ln(k ; 1)  ck 2 2 2 j =1 k X i=1 (3) alapjn jLj  (i) i  k X j =1 i  21 k 2 (2) (3) 3 p n~ k  pn~ pce~ = c e~: 4 n~ 4 3 Teht jLj  e~  e=5, ha c < 1=4. Msrszt az illeszkedsek szma alulrl becslhet, mert minden y ; j = = sr (x ; i) egyenes illeszkedik a rcs minden r-edik oszlopban egy cscsra s (2) szerint: I p X 2 rs) = 1 srk lnko( 1 p p k n~ = X n~ n~  n~ ck = cc = n~ = e~ = : jLrs j r ( r ) r r r 2 2 2 2 3 2 3 2 3 =1 Ebbl I  c c2 3 n = e = feltve, hogy n  20 e  5 s c < 1=4 mellett (1) teljesl. A konstans faktor

vlaszthat olyan kicsinek, hogy a kimarad vges sok esetet is jl becsljk. = 2 2 3 2 3 2 14 2. Kvetkezmnyek A Szemerdi-Trotter ttelnek szmos hasznos alkalmazsa ismert. Tbb rgi problma oldhat meg egyszer en a segtsgvel. Egy alkalmazsi terlet az additv szmelmlet. Legyen A R ; f0g vges szmhalmaz, jAj = n. Knnyen lthat, hogy megadhat A gy, hogy jA + + Aj vagy jA Aj komplexusszorzatok szmossga legfeljebb 2n ; 1 legyen, (pldul szmtani vagy mrtani sorozattal). De szmtani sorozatok komplexusszorzata, mrtani sorozatok komplexussszege nagy lesz Erds s Szemerdi 19] maxfjA + Aj jA Ajg-ra kerestek als becslst. Azt sejtettk, hogy maxfjA + + Aj jA Ajg = (n ; ). Ksbb Nathanson adott (n = )-es als becslst, majd Ford (n = )-t. !ltalnosabban Ruzsa Imre 26] problmja az, hogy valamely f szigoran konvex fggvnnyel mi a legjobb als becsls maxfjA + Aj jf (A) + f (A)jg-ra. A Szemerdi-Trotter ttelt hasznlva Elekes Gyrgy s Ruzsa Imre 15]

tallta a kvetkezt. 2 32 31 16 15 2.1 llts: Legyen A R vges szmhalmaz, (jAj = n). f szigoran konvex vagy konkv fggvny. Ekkor komplexus-sszeggel maxfjA + Aj jf (A) + f (A)jg = (n = ): 5 4 Mg ltalnosabban: R vges szmhalmaz, (jAj = n jB j = m). 2.2 Ttel: Legyen A B f szigoran konvex vagy konkv fggvny, (A Dom(f )). Ekkor komplexussszeggel p jA + Aj jf (A) + B j = (n m): 2 Bizonyts: Legyen A = fa  a  : : : an g, B = fb  b  : : : bm g. De niljuk a kvetkez nm darab fggvnyt: fij (x) := f (x ; ai) + bj  i 2 1 n] j 2 1 m] Az fij fggvny grfja az f (x) szigoran konkv (konvex) fggvny grfjnak eltoltja. Az fij fggvnyek grfja klnbzk s brmely kettnek a metszete legfeljebb egy pontbl ll. Minden fij fggvny A + A legalbb n elemt viszi f (A) + B -ba (tudniillik minden k 2 1 n]-ra (ak + aj )-t). Ksztsk el az (A + A) (f (A) + B ) N elem pontrcsot R -ben. Itt az fij fggvnyek nm legalbb n pont grbt rnak le s n n 

j(A + A)j j(A A)j = N: 1 2 1 2 15 2 A Szemerdi-Trotter ttel s az 1.8 megjegyzs szerint   jA + Aj jf (A) + B j] nm = jffij gj = O n Ez pedig a kvnt lltst szolgltatja. 2 3 2 Ebbl a 2.1 llts azonnal addik, hiszen legyen B = f (A), ekkor n=2  (n = ), ahonnan  jf (A)j  n. A 22 ttel szerint jA + Aj jf (A) + f (A)j = maxfjA + Aj jf (A) + f (A)jg = (n5=4): 5 2 A Szemerdi-Erds problmra f (x) = log(x) vlasztssal kapunk vlaszt 14] a 2.1 lltst alkalmazva: 2.3 llts: Legyen A R ; f0g n elem szmhalmaz. Ekkor a komplexus-sszegre s komplexusszorzatra maxfjA + Aj jA Ajg = (n = ): 5 4 2 Rgi krds, hogy Rd-ben adott vges sok ponthoz s egy rszhalmazhoz hny hasonlsgi transzformcija van a trnek, amivel a rszhalmaz kpe a vges halmazban marad. Ismert, hogy a skon n pont alaphalmazzal s x C elem rszhalmazzal legfeljebb O(n ) hasonlsg fordulhat el s bizonyos esetekben el is fordul (n ). 2 2 2.4 llts: Legyen adott R-ben egy Cn

pontbl ll P halmaz, (C  2) Legyen O P , ahol jOj = n. Ekkor R azon hasonlsgainak szma, melyek O-t P -be kpezik, O(n). Bizonyts: R minden hasonlsga elll x 7! ax + b (a b 2 R) alakaban. brzoljuk ezeket a fggvnyeket R -ben egyenesekkel Tekintsk az O P R R pontrcsot. Ha R egy hasonlsga O ; t P -be viszi, akkor a neki megfelel egyenes n pontra illeszkedik R -ben. A Szemerdi-Trotter ttel szerint a Cn n pontbl n-et tartalmaz egyenesek szma a skon legfeljebb C (N ) = O(n): n 2 2 2 2 3 2 Ez az korlt aszimptotikusan les Cn elem szmtani vagy mrtani sorozatokra s n elem kezdszeleteikre. 16 2.5 Definci : Legyen adott Rd -ben egy ponthalmaz Akkor neveznk egy k dimenzis an alteret kifesztettnek, ha az tartalmaz k +1 darab an fggetlen pontot. Beck Jzsef 3] bizonytotta a kvetkezt. 2.6 Ttel: Legyen n klnbz pont halmaza R2 -ben P Ekkor ltezik c > 0 konstans, hogy vagy a P ltal kifesztett egyenesek szma elri cn -et vagy valamely

egyenes P legalbb n=100 pontjt tartalmazza. 2 Beck ezt a ttelt Szemerditl s Trottertl fggetlenl ltta be azzal a segdttellel, hogy apskban adott n klnbz pontra s e klnbz egyenesre a legalbb t (t 2 2 2n) pont egyenesek szma legfeljebb n =t : . A SzemerdiTrotter ttelnl gyengbb llts is elg ennek igazolsra 2 2 05 Bizonyts: Jelljk lj -vel (j 2 J ) a ponthalmaz ltal kifesztett egyenesekre illeszked pontok szmt. A pontprok szmra termszetesen igaz az albbi egyenlsg: X lj  n = 2 : j 2J 2 A bal oldali szummt ngy rszre bontjuk.     X X l lj  j P =  P = 2 p 2 l2  l2  n     X X l lj : j P =  P = 2 2 p l 2 n= n l 2 nn= Azt fogjuk beltni, hogy P -ben s P -ban "kevs# pr van.  i  X X lj  X 2 P =  e j  2 2 p ci l 2  +1 ci  n   X n 2i  X 1 ; i  C 2 i 2  2Cn 2 < 4 n2  ci ci ha c-t elg nagynak vlasztjuk.    i p  X X X l j p n 2 2n  P =  e 2 2 i l 2 p n +1 p n 2 pn= l  n= 1 2 2 2c ] j

j 2c 2 ] 4 3 j  2 100] j 2  100 ] 3 +1 2 2 i j 2i 2i ] 2 +1 2i 2 2 3 +1 3 2i 0 j 2 i j 2 i 2 100 2i 2 2 ] 17 100] 2  X 2 pn= 2i 2 Eszerint 100] p i 2 i pn 2 2n 2 2 2n +1  2 pn= 2i 2 100]   n : 4 2 2i < 1 X  8n = 3 2   P + P > 12 n2  c azaz vagy van legalbb ;n n=100 pont egyenes, vagy P = 0 s a maximum ;  2 pont pontpr. De egy ilyen egyenesen legfeljebb pontpr egyeneseken van ;n; ; van. Ezrt az egyenesek szma legalbb = (n ) 1 1 2 4 4 2 1 2 2 2c 2 2c 2 1 2 2 2.7 Ttel: Legyen n klnbz pont halmaza Rd -ben P Tekintsk az ltaluk kifesztett sszes hiperskot. Ekkor lteznek A B C > 0 csak d-tl fgg konstans, hogy valamely hiperskra legalbb An pont illeszkedik, vagy van legalbb Bnd hipersk amelyekre legfeljebb C pont illeszkedik. Bizonyts: Indukci a dimenzi szerint. d = 2-re a 25 ttel bizonytsa adja az lltst. Tegyk fel, hogy igaz a ttel minden

d-nl kisebb dimenzis trben (d  3). Lssuk be Rd-ben. Vettsk P -t egy olyan skra, amely egyetlen legalbb kt pont egyenesre sem merleges. A vetlet legyen P 0 A 2.5 Beck ttel alapjn lehet, hogy n=100 pont egy egyenesen van a P 0 vetletben. Ekkor P -ben van n=100 pont egy hiperskon Legyen A  1=100  s a ttelnk azonnal teljesl ebben az esetben. Klnben van legalbb cn kifesztett egyenes P 0-ben. Azaz P -ben is van legalbb cn kifesztett egyenes. Minden p 2 P ponthoz vegynk egy hp hiperskot, ami nem illeszkedik p-re s nem prhuzamos egyik kifesztett egyenessel sem. Vettsk erre a tbbi n ; 1 pontot. gy legalbb 2cn vetlet pont keletkezik az n darab hiperskon Vegyk azokat a hp skokat, amelyeken legalbb cn vetletpont van. Ilyenbl legalbb ;c c n-et tallunk. Az indukcis feltevs szerint vagy valamely hp-n van egy (d ; 2)-dimenzis hipersk, amelyre legalbb Ad; cn pont illeszkedik, azaz P -ban egy hiperskra illeszkedik ennyi pont. Ekkor A  Ad; c

vlasztssal kszen vagyunk vagy minden ilyen hp-n van legalbb Bd; (cn)d; darab (d ; 1)-dimenzis an altr amelyre legalbb d ; 1, maximum Cd; vetletpont illeszkedik. 2 2 2 1 1 1 1 1 1 18 Denci: Azt mondjuk, hogy egy p pontbl egy r illszked hipersk D pontnak ltszik, ha a hp-beli vetlete D pont. Itt ;c c n darab P -bei pontbl sszegezve a legalbb D pontnak ltsz hiper;1 skokat B ;;1cc nd-ot kapunk, ahol D 2 d ; 1 Cd; ; 1]. Egy P -beli skot tbbszr is szmolhatunk gy. Azt szeretnnk, hogy csak konstans sokszor szmoljuk ezeket a kifesztett hiperskot. 1 d d 1 1 Segdttel: Ha egy D -nl tbb pont hipersk legalbb D pontjbl ltszik D-nl kevesebb pontnak, akkor ezek a pontok egy egyenesen vannak. Bizonyts (Segdttel): Legyen R egy ilyen hipersk azon pontjainak hal2 2 maza, amelyekbl a hipersk D-nl kevesebb pontnak ltszik. Ha R pontjai nem kollinerisak, akkor vegynk kt R-beli pontot. R minden pontja e kt pontra illeszked,

egyenknt maximum D egyenes egyenesnyalbon van. Ez maximum (D ; 1) pont lehet plusz a kt pont egyenesre illeszked pontok. Ez utbbiak is D-nl kevesebben vannak, mert egy harmadik R-beli pontbl ez az egyenes ltszik maximum D pontnak. gy a skon legfeljebb D pont lehet. 2 Ha R pontjai kollinerisak, akkor a hipersk egy egyenes s rajta kvl maximum D pont lehet. Becsljk a kvetkez hrmasokat: (sk, egyenes,pont), ahol a sk illeszkedik az egyenesre, az egyenes illeszkedik a pontra s az egyenesnek legalbb D  Cd; pontja van. Az adott (pont,egyenes) prokhoz tartoz skok szmt mindig fellrl becslhetjk nd; -vel. gy elg a (pont,egyenes) prokat becslni, ahol az egyenesnek legalbb D pontja van. A Szemerdi-Trotter ttel alapjn a legalbb p p j pont egyenesek szma legfeljebb nj32 , ha j 2 2 n] s legfeljebb nj , ha j  n. Ezrt a keresett (pont,egyenes) prok szma: pn n X X n n  n + n ; n + 1 n log n  4 n  D D + nj + j D D 2 D j j pn 2 2 2 1 2 2 2 3 3

=1 2 2 2 2 2 2 = ha n elg nagy. Vlasszuk D-t gy, hogy 4 D2  B ;;1cc teljesljn ;1 Ekkor van legalbb B ;;1cc nd (pont,hipersk) pr, hogy a pontbl a hipersk D-nl kevesebb pontnak ltszik, de legfeljebb D pontja van, ha n elg nagy. Egy skot gy legfeljebb D -szer;1szmolunk. Van teht legalbb B ;;1ccD2 nd kifesztett hipersk, amin legfeljebb D pont van, ha n elg nagy. Legyen C = D s tallhat olyan B > 0, hogy mr kis n-ekre is van legalbb B kifesztett hipersk, amin legfeljebb C pont van. 1 1 2 d d 1 1 2 ;1 d d 1 2 2 1 d 2 (1 d ) 2 2 19 A Beck ttelnek szmos hasznos kvetkezmnye van, amelyek rgi problmkra adnak feleletet. DA Dirac 9] s TS Motzkin 22] krdeztk 1951-ben, hogy a skban adott n nem-kollineris pont kztt mindig van-e olyan, amelyre legalbb cn kifesztett egyenes illeszkedik alkalmas c > 0-val. A vlasz igenl. Beck ttelbl knnyen levezethet az albbi 2.8 Kvetkezmny: Legyen adott Rd -ben n klnbz pont,

nem mind egy hiperskon. Ekkor van kztk olyan, amelyre legalbb cn kifesztett hipersk illeszkedik, alkalmas c > 0, csak a dimenzitl fgg konstanssal. Bizonyts: Ha az ltalnostott 2.7 Beck ttel lltsa szerint van legalbb Bnd kifesztett hipersk, akkor van olyan pont, amelyre legalbb dBnd; illeszkedik, hiszen minden kifesztett hiperskon legalbb d pont van. Ha van egy olyan S hipersk, amire legalbb Ad; n pont illeszkedik, akkor d = 2 esetn egy S -en kvli pontra legalbb Ad; n egyenes (itt ez a hipersk) illeszkedik. d  3 esetn pedig indukci szerint S -ben van egy p pont, amire legalbb cd; n darab (d ; 2)-dimenzis hipersk illeszkedik. Vegynk egy q pontot S -en kvl, ez S hiperskjaival Rd-beli hiperskot feszt ki. gyp-re legalbb cd; n hipersk illeszkedik. 1 1 1 1 1 2 2.9 llts: Legyen adott n klnbz pont R2 -ben Az ltaluk kifesztett egyenesek szma legyen e. Tegyk fel, hogy minden kifesztett egyenesre legfeljebb n ; k adott pont

illeszkedik, (k 2 0 n ; 2]) Ekkor e > ckn, alkalmas c > 0 konstanssal. Bizonyts: k = 0-ra az llts trivilis. Ha a 2.5 Beck ttel szerint van B n egyenes, akkor c < B megfelel Ha van egy legalbb n=100 pont S egyenes, akkor n=100  n ; k, vagyis k  n(1 ; 1=100). Vegynk dk=100e pontot S -en kvl Ezek S pontjaival egytt kifesztenek legalbb   k (n ; k) ; dk=100e  k (n ; k ; dk=100e)  k n 100 2 100 100 200 klnbz egyenest. 2 2 2 2 2.10 Kvetkezmny: Ha R2-ben adott n klnbz pont s valamelyik egyenesre k pont illeszkedik, akkor a kifesztett egyenesek szma ((n ; k)k). Bizonyts: Egy egyenesre legfeljebb maxfk n ; k + 1g pont illeszkedhet gy van c(maxfnk n(n ; k + 1)g  ck(n ; k) kifesztett egyenes. 20 2 G. Purdy 1951-es sejtse szerint ha R -ban n klnbz pont, ami nem mind egy skon vagy kt kitr egyenesen van e egyenest s s skot feszt ki, akkor n ; e + s + 2  0. Ez ltalnos esetben azta sem nyert bizonytst de ha igaz lenne,

az kvetkezne belle, hogy e = O(s). Purdy 25] beltta a kvetkezt 3 2.11 Ttel: Legyen adott R3-ban n klnbz pont nem mind egy skon vagy kt kitr egyenesen. Legyen e ill s az ltaluk kifesztett egyenesek ill skok szma. Ekkor van olyan pont, amire legalbb ce sk illeszkedik alkalmas c > 0, konstanssal. Bizonyts: (1) Ha egy skra sem illeszkedik c0n=2-nl tbb pont (a 2.8 ttelbeli c konstanssal) Ekkor nem minden pont illeszkedik egy egyenesre Ezrt 28 szerint van egy p pont amire legalbb c0n kifesztett egyenes illeszkedik. Vettsk p-bl egy p-t nem tartalmaz S skra a tbbi n ; 1 pontot S -ben legalbb c0n klnbz vetletpont van. S -en egy egyenesre legfeljebb c0n=2 vetletpont esik A 29 llts szerint ekkor S -ben van legalbb c00(1=2)n n kifesztett egyenes. Teht van (n) darab p-re illeszked sk (2) Ha valamely S skon van legalbb c0n=2 pont. Legyen l0 az S kifesztett egyeneseinek szma. Ekkor egy p 62 S pontra illeszked skok szma legalbb l0 Ha S

pontjainak legfeljebb a fele van egy egyenesen, akkor a 2.9 llts szeint l0  c00(1=2)(c0 n=2) = (n ) = (e). Tegyk fel teht, hogy S egy L egyenesn legalbb c0=4n pont van. Most jS j = n ; k s jLj  (n ; k )=2 = c0n=4. Az S -en kvli pontokat jelljk r  : : : rk -vel. (2:a) Ha minden i-re ri egy L-re illeszked T skon van legyen T egyeneseinek szma l00. A 210 kvetkezmny szerint l00  c00kn A nem az S vagy T skokban lv egyenesek egyik pontja egy ri pont, ezrt l0 + l00  l ; nk  l ; l00=c00, ezrt l0 + l00 = (l), maxfl0 l00g = (l). Teht vagy egy S -en kvli pontra vagy egy T -n kvli pontra illeszkedik (l) sk. (2:b) Ha minden i-re ri illeszkedik egy L-tl kitr L^ egyenesre, akkor van egy p pont, ami nem illeszkedik sem L^ -re sem L-re. p pont egy-egy L ill L^ -beli ponttal klnbz skokat feszt ki. Ezrt a p-re ileszked skok szma sp  kc0n=4 Ha l  2nk, akkor sp  (l). Ha pedig k  2nk, akkor l0  l ; nk  l=2 s brmely S skon kvli pontra illeszkedik

l0 sk. 2 2 2 1 21 T3 T2 T1 T4 T5 S L (2:c) Ha az ri pontokat fedik az L-re illeszked T  : : : Tt skok, akkor a 2.8 kvetkezmny szerint van egy ri = p 62 S , amit legalbb c0k egyenes kt sssze valamely ms ri ponttal. Feltehetjk, hogy ezen egyenesek kz l c0k=2 valamely ms Tj skbeli ri pontba vezet klnben az ri pontok fele p skjban lenne s egy msik Tj skbeli q pontbl vezetne p skjba legalbb c0k=2 egyenes. A 210 kvetkezmny szerint ez a c0k=2, L-tl kitr egyenes s L pontjai c00(c0k=2)(c0n=4) darab klnbz, p-re illeszked skot fesztenek ki. A p-re illeszked skok szmra sp  cnk sp  l0 Ebbl (1 + (c); )sp  ln0 k  l, ahonnan sp = (l) 1 1 2 2.12 Ttel: Legyen adott R3 -ban n klnbz pont, nem mind egy skon Legyen e ill. s az ltaluk kifesztett egyenesek ill skok szma Ekkor e  cns alkalmas c > 0 konstanssal. 2 Bizonyts: (1) Ha nincs ;n=2 pont egyenes, akkor a 2.9 llts szerint e  c00(1=4)n Ugyanakkor s  n  n =6.

gy e  (c00=4) n = (ns) (2) Ha egy L egyenesre legalbb n=2 pont illeszkedik, akkor legyen jLj = n ; k. A kifesztet skok szmt becslni tudjuk a kvetkezkppen, s  k =6 + 1=2(n ; k)k + k  12 k  mert a kifesztett skokon legfeljebb kt L-beli pont lehet. Egy skot hrom Len kvli pont vagy egy L-beli s kt L-en kvli vagy L s egy rajta kvli pont 2 3 3 2 2 3 4 2 22 2 feszt ki. Hasonlkppen becslhet alulrl a kifesztett egyenesek szma az L-beli pontot L-en kvlivel sszekt egyenesek szmval:   1 k n = (ns): e  k(n ; k) ; k2  41 kn ahonnan e  16 2 2 2 2 23 3. Kombinatorikus grbk Az 1. fejezetben felsoroltuk, hogy az egyenes mely tulajdonsgait hasznlta ki a Szemerdi-Trotter ttel Szkely-fle bizonytsa. Hrom felttel enyhtse csak konstans faktorral rontotta a fels becslsnket. Most a msodik felttelt vizsgljuk meg tudniillik "kt pontra legfeljebb K grbe illeszkedik#. A felttelt teljesen elhagyni nem lehet, mert akkor

mind az e darab grbe illeszkedne az n adott pontra I = ne illeszkedst produklva. Ha azt mondjuk, hogy k diszjunkt pontra legfeljebb K 2 N grbe illeszkedik, akkor mr nem m kdik a Szkely fle bizonyts, hiszen az Euler ttel nem igaz, ha megengednk akrhnyszoros leket. Igaz viszont a kvetkez ttel az emltett grbeosztlyra, amit most pontosan de nilunk. 3.1 Definci : Az euklideszi tr egyszer 3 grbinek E osztlyt k -param- ter nek nevezzk, ha tallhat olyan s 2 N, hogy Brmely k ponthoz legfeljebb s darab E -beli grbe van, amely mindegyikre illeszkedik, E brmely kt eleme legfeljebb s pontban metszi egymst. 3.2 Ttel: Legyen adott R2-ben egy n elem P ponthalmaz s egy e elem , k-paramter E grbeosztly. Ekkor a ltrejv illeszkedsek szma I = O(nk= k; e k; = k; + n + e): (2 1) (2 2) (2 1)) Egyenesekre (k = 2), a korlt megegyezik a Szemerdi-Trotter ttel korltjval. A ttelt Pach Jnos s Micha Sharir ltta be 1996-ban 24] Tipikus k-paramter

grbeosztly a k vals paramter algebrai grbk halmaza. Erre a grbeosztlyra mr 1992-ben beltta a ttelt Pach s Sharir ms technikkkal 23]. Itt a Szkely-fle bizonytst ltalnostjk Felhasznlnak mg egy tisztn kombinatorikus korltot is az illeszkedsek szmra. Ez Kvri, TSs s Turn 20] 1954-es eredmnye 3.3 Lemma: Ha egy e n-es 0 ; 1 mtrix nem tartalmaz k (s +1)-es csupa 1 rszmtrixot, (ahol k 2 1 n ; 1] s + 1 2 1 e ; 1]), akkor az egyesek szma I  ke + s =k ne ; =k : 1 3 nmetszs nlkli 24 1 1 Bizonyts: Legyen I^ = ke + s1=k ne1;P1=k  s legyen az i 2 1 e]-edik sorban lv egyesek szma ai. Tegyk fel, hogy ei ai > I^ Rendezzk t a sorokat gy, hogy valamely m 2 1 e]-re a  a  : : : am  k, a tbbi kisebb k-nl. Ekkor a Hlder-egyenltlensgbl =1 1 e   X ai i=1 2 m   X ai k =i =1 m X 1 k k  k! i (ai ; k)  =1  e !k   e ;k ;k k k; X e e n : e ;k X k ^ ; ek) = a a ( I sn e s i; i ; mk > k! i k! k! k i m Teht ha

minden sorbl kivlasztunk k darab egyest az sszes lehetsges mdon, akkor tbb mint s-szerest kapjuk a lehetsges mintzatoknak. Azaz kivlaszthat s + 1 sor, amelyben ugyanabban a k oszlopban egyesek vannak 2 1 1 =1 = 1 1 +1 3.4 Kvetkezmny: R2-ben adott n klnbz pont halmaza s egy e elem , k-paramter grbeosztlyra a ltrejv illeszkedsek szma O(ne ; 1 + e): Bizonyts: Alkalmazzuk a lemmt az n pont s az e grbe illeszkedsi mtrixra. Ha lenne a mtrixban k (s + 1)-as csupa 1 rszmtrix, akkor lenne k pont, amire s + 1 grbe illeszkedik. Az egyesek szma pedig az illeszkedsek szmval egyenl. 1 k Bizonyts (3.2 ttel): Hagyjuk el az sszes olyan grbt, ami nem tartalmaz legalbb k pontot. Ezzel az illeszkedsek szmt legfeljebb (k ; 1)nnel cskkentettk, a krdses nk= k; e k; = k; mennyisg pedig nem ntt Legyen dA = I=n az egy pontra illeszked grbk tlagos szma, p 2 P ; re dp a p-re illeszked grbk szma. 1. Eset Tegyk fel, hogy minden p 2 P -re

dp 2 d 2d], ahol d 2 dA =2 dA ] Ksztsnk a (P  E ) rendszerhez egy (G E ) tbbszrs l geometriai grfot: G = P , tovbb ha p q 2 P egy grbn van s a kzttk lv egyik grbedarabon legfeljebb k ; 2 pont van, akkor legyen a grf le ez a grbegarab4 . Ekkor I   jE j < (k ; 1)I . Ksztsnk egy kisebb (G H ) gfot is. H -t E -bl gy kapjuk, hogy kitrl1 ; ; 1 jk E minden Ad -nl tbbszrs lt valamely ksbb megadand A > 0 konstanssal. Azt szeretnnk beltni, hogy jH j = (I ) is igaz. Ehhez elg lenne igazolni, hogy minden p 2 P = G pont H -beli foka, dH = (d) mert akkor jE j  n (d) = = I teljeslne. (2 1 4 1) (2 k Az lek gy egymsba rhetnek 25 2) (2 1) q p Legyen p q 2 P -re E (p q)  E a p-t s q-t sszekt E -beli lek halmaza E (p) a p-bl indul lek halmaza E (p 7! q) pedig az szes olyan l, ami egy pq sszekt grbn van, p-bl indul de vgpontja nem q. Itt dH (p) = jE (p) H j. Egy pr l legfeljebb (2k ; 3)-szor szerepel

valamely E (p 7! q) lhalmazban, mert ehhez q-nak a pr l grbjn P kell lennie maximum (k ;1)-edik pontknt s q 6= r. gy jE (p)H j  (1=(2k ;3)) q2P jE (p 7! q)H j pq 2 H esetn becsljk jE (p 7! q) H j-t grbnknt jE (p q)j-val. A becsls csak azokon a grbken nem m kdik, ahol semelyik p-bl indul pq-n kvli l sincs H -ban. Legyen R = fr 2 P : pr 2 E (p 7! q) pr 62 H g. Erre dG (p)  2d(2k ; 1) < 4k d ;1 1 : jRj  A Ad ; ;1 1 Ad ; ;1 1 De p q s (k ; 2) darab R-beli pont legfeljebb s grbre illeszkedhet, ezrt    k; jRj 4 k ; ;1 1 : jE (p 7! q ) H j  jE (p q )j ; s  jE (p q )j ; s Ad k;2 A(k ; 2)! k 1 1 k k 2 1 k Ez pedig nagyobb jE (p q)j-nl, ha A-t elg nagynak vlasztjuk, mert pq 2 H esetn jE (p q)j  Ad ; ;1 1 . $sszefoglalva 1 X jE (p 7! q) H j  1 X jE (p q)j  jE (p) H j  2k ; 3 q2P (2k ; 3) q2P 2 1 jE (p)j  d(k ; 1)  d=4:  (4 ; 6k) 4k ; 6 Ezzel jH j = (d). ;  A (G E ) s (G H ) lei egy grbe egy tetszleges pontjt legfeljebb

k szeresen fedik le. Ezrt ltezik (G H 0) ;(G H ) rszgrf, aminek lei nem fedik tbbszrsen a grbket s jH 0j  jH j= k . 1 2 1 k 2 2 26 Ha jH 0j < 5nAd ; 1;1 1 , akkor I = O(jH j) = O(jH 0j) = O(nd ; ;1 1 ). Itt d   I=m s I = O(Id; ;1 ) miatt d = O(1). Ha pedig minden pont konstans sok grbre illeszkedhet, akkor I = O(n). 1 ; 0 Ha jH j  5nAd ;1 , akkor (g H 0) grfra alkalmazhatjuk az 1.10 ttelt s  !  ! 0 j H j I cr(G H 0 ) = = : n Ad ; ;1 1 n (I=n) ; ;1 1 ; Msrszt cr(G H 0 )  s e , mert kt grbe legfeljebb s pontban metszi egymst. 1 1 Innen I ; ; ;1 = O(e n ; ; ;1 ), ahonnan I = O(nk= k; e k; = k; ). 2.Eset Tetszleges P  E esetn legyen P  azon pontok halmaza, melyek legfeljebb I=(2n) grbre illeszkednek. A P  E kzti illeszkedsekre I (P  E )   I=2, ezrt elg I (P ; P   E )-t becslni. Becsljk az egyes pontokra illeszked grbk szmt. Ehhez osszuk P -t diszjunkt ponthalmazokra:   P = Pi  ahol Pi = fp 2 P ; P  : dp 2 2i;

I=n + 1 2i I=n]g i2N s legyen ni = jPij. Most mr becslhetjk a Pi-beli pontok s az sszes grbe illeszkedst az 1.eset alapjn, hiszen I  ni mini dp > ni2i; I=n szerint ni < < n=2i; . gy 1 1 k k k 1 k 3 1 2 3 (1 k ) 2 2 (1 2 3 1 2 k ) k k (2 1) (2 2) (2 1 1 i 1 k; e k; = k; + n + e) = I (Pi E ) = O(nk= i i = O(2;ik= k; nk= k; e k; = k; + ni + e): (2 (2 1) 1) (2 (2 2) (2 1) (2 1)) 2) (2 1)) Alkalmazzuk a 3.3 kvetkezmnyt azokra a Pi-kre, amlyekre j fPi : nki < e=2i gj = X ni = O(e =k ): 1 n <e=2 k i i Ezek sszes illeszkedse O(ne ; 1 + e) = O(e). Ha nki  e=2i , akkor k; e = e = k; e k; = k;  2i= k; nk= e k; = k; = i 1 1 (2 1) (2 k 2) (2 1) (2 1) (2 1) (2 O(2;j k; = k; nk= k; e k; = k; ): 2) (2 ( 1) (2 1) (2 27 1) (2 2) (2 1) 1) 1)) Az ilyen Pi-kre X i I (Pi E ) = X i O(2;j k; = k; nk= k; e k; = k; + ni)+ ( 1) (2 1) (2 1) (2 2) (2 1) = O(nk= k; e k; = k; + n): (2 1) (2 2) (2

1) 2 Ennek a ttelnek is lteznek ekvivalens alkajai, itt ltjuk be az 1.2 llts megfeleljt: 3.5 llts: Legyen adott R2 -ben n pont s egy e elem , k paramter grbeosztly. Ekkor az illeszkedsek I szmra egyszerre teljesl (1) I = O(nk= k; e k; = k; + n + e) (2 1) (2 2) (2 1) n  e  nk eseten I = O(nk= k; e k; = k; ) p (2) (2  1) (2 2) (2 1)  k et = O t nk; + nt  ha t 2 k n] (3) 2 1 ahol et jelli a legalbb t pont grbk szmt. Bizonyts: (1) ) (2) n  e  nk esetn n = nk=(2k;1)n(k;1)=(2k;1)  p  nk=(2k;1)e(2k;2)=(2k;1) s e = e(2k;2)=(2k;1)e1=(2k;1)  e(2k;2)=(2k;1)nk=(2k;1) .  p  (2) ) (3) Beltjuk, hogy 2  t  D n esetn et = O t2n;1 , (D > 1). p Legyen C > 0 olyan, hogy n  e  nk esetn I < C (nk= k; e k; = k; ) teljesljn. Indirekt tegyk fel, hogy van e = (CD) k; nk =t k; darab k-paramter grbe legalbb t ponttal. pItt az illeszkedsek szma I  et  (CD) k; nk =t k; . p Msrszt ha t 2 CD C n], akkor n  e  nk

teljesl, s (2) szerint I < < C (nk= k; e k; = k; ) ;C k; D k; nk =t k; , ellentmonds. Ha pedig t 2 2 k CD ; 1], akkor et  s nk = O t2n;1 . ;  p Most azt ltjuk be, hogy t 2 pD n + 1 n] esetn et = O nt . Tudjuk, hogy et  eDpn = O( Dpnn 2 ;1 ) = O( n). Tekintsk az n pont s az et legalbb t pont grbe rendszert. Ez nem felttlen felel meg (2) felttelnek Ezrt osszuk fel az n pontot dn=et e darab legfeljebb et elem rszre. Ezekre mr (2) alkalmazPdn=e2 e hat s az sszes illeszkeds: I = i Ii = dn=et eO((et )k= k; et k; = k; ) = = O(n). Teht ett  I  O(n), s gy et = O( nt ) k k (2 2 1 2 1) (2 2) (2 1 2 (2 1) (2 2) (2 1) 2 1 2 2 2 1) 1 2 2) (2 1) 2 k k k ( ) k 2 =1 2 t 28 2 (2 1) (2 2 (3) ) (1). Tudjuk, hogy t 2 k Dpn] esetn et  C t2n;1 Becsljk fellrl az illeszkedsek szmt. Legyen l a legkisebb olyan termszetes szm, hogy k C k; l nk;  e: Ekkor l = O(nk= k; =e = k; ) s az 1 l]-beli pontszm grbk sszes

illeszkedseit fellrl becsli pn  k= k;  Z Dpn DX k n nk dt = (k ; 1)e + le + t k;  (k ; 1)e + eO ne = k; + t k; l t l k k 2 1 2 (2 1) 1 (2 2 1 1) 1 (2 1) 1 (2 1) 2 1 =   1 ; 1 k ; k ; l D nk;   O(e + nk= k; e k; = k; ): p A D pn-nl tbb pontp grbket osszuk fel olyan darabokra, amelyeken legalbbpD n legfeljebb 2D n pont van. A rendszerre ekkor isp igaz, hogy eDpd = p = O( n). Az ilyen grbk sszes illeszkedse teht D nO( n) = O(n) = O(e + nk=(2k;1)e(2k;2)=(2k;1)) + O(nk ) (2 1) (2 2 2 2) (2 1) 2 2 1 2 29 4. Tbb dimenzi s ltal nos t sok A Szemerdi-Trotter ttel ltalnostsa hrom- vagy magasab dimenziban tbbfle alakot lthet. R -ban pontok s egyenesek illeszkedsre persze a Szemerdi-Trotter fle fels becsls rvnyes lesz. Vettsk ugyanis a pontokat s egyeneseket egy olyan skra, amely nem prhuzamos egy egyenessel sem s nem merleges semelyik pontpr egyenesre s semelyik egyenespr (esetleges) skjra. Ekkor diszjunkt

pontok vetletei diszjunkt pontok lesznek, diszjunkt egyenesek vetletei diszjunkt egyenesek. A vetts az illeszkedst megtartja Ez a becsls les is, hiszen ha a pontok mind egy skban vannak, megismtelhetjk az Erds fle konstrukcit. Pontok s skok illeszkedsnl a nehzsget az okozza, hogy n kollineris pont s az egyeneskre illeszked e sk ne illeszkedst ad. Ennl jobb becslsek elrshez tovbbi feltteleket kell szabni a pontok s skok elhelyezkedsre. 3 4.a Kifesz tett s kok Az egyik lehetsg az, hogy az n klnbz ponthoz csak olyan skokat engednk meg, amelyeket a pontok kifesztenek, azaz tartalmaznak hrom nemkollineris pontot. Ebben az esetben Clarkson, Edelsbrunner, Guibas s Sharir 11] bizonytottk egy rekurzv eljrssal a kvetkezt. 4.1 Ttel: Legyen adott R3-ban n klnbz pont s a pontok ltal kife- sztett e sk. Ekkor az illeszkedsek szma I = O(n + e = n log n) 2 2 3 4.2 Segdttel: Legyen adott klnbz pontok Pa s Pb diszjunkt hal-

mazai. Legyen na = jPaj, tovbb jPaj s jPbj klnbsge legfeljebb egy E legyen e darab sk, melyeket Pa  Pb kifeszt, de Pa vagy Pb nem. Ekkor Pa  Pb s E kztti illeszkedsek szma: I = O(na + e = na). 2 2 3 Bizonyts: Az E -beli skok illeszkednek egy Pa -beli pontra s egy Pb -beli kifesztett egyenesre, vagy egy Pa-beli kifesztett egyenesre s egy Pb-beli pontra. Most nzzk csak az elbbieket. Szmoljuk az ilyen skok illeszkedseit Fels becslst kapunk, ha sszegezzk minden p 2 Pa ponthoz a pontra s egy Pb ltal kifesztett, p-t nem tartalmaz egyeneshez tartoz E -beli skok (ezeket jellje Ep) illeszkedseit. (gy esetleg egy skot tbbszr szmolhatunk) Vegynk egy p 2 Pa pontot. Vettsk Pb pontjait egy tetszleges, p-t nem tartalmaz hp skra, a vetlet legyen Pb0 . Nyilvn jPb0 j  nb Az Ep -beli skok metszetei a vetletskon kpezzk az Ep0 egyeneseket, (jEp0 j = ep  e). 30 p hp A Szemerdi-Trotter ttel szerint a hp skon I (Pb0 Ep0 ) = O(n = ep= +

nb) 8p 2 Pa: 2 3 2 3 b $sszegezve ezen egyenlsgeket minden p 2 Pa-ra a Hlder-egyenltlensg segtsgvel: n X X = = O(nb ep + nb)  O(( ep= )nb = + nb)  p2P i  O(e = na= nb = + na nb )  O(na + na e = ): Ugyangy becslve a p 2 Pb pontokra illeszked skok sszes illeszkedseit: a 2 3 2 3 2 3 2 3 =1 a 2 3 1 3 2 3 2 2 3 I = O(e = na= nb = + nanb ) + O(e = nb = na= + nanb) = O(na + e = na) 2 3 1 3 2 3 2 3 1 3 2 3 2 2 3 2 Bizonyts (4.1 ttel): Osszuk kt kzeltleg egyforma elemszm rszre, Pa Pb-re az n pont halmazt. Ekkor az albbi rekurzv formult kapjuk az illeszkedsek szmra: I (n e) = 2I (n=2 e) + O(n + ne = ) 2 2 3 A rekurzv osztogatst akkor hagyjuk abba, ha (1=2)e =  ni  e = . Ekkor I (ni e)-t az O(n ) korlttal becslhetjk. (Ez mindig igaz, hiszen n pont van s ;n egy pontra legfeljebb sk illeszkedhet, mert egy skot mg kt an fggetlen 1 3 3 2 31 1 3 pont feszt ki). Most O(n ) = O(e) = O(e = e = ) = O(ne = ) Ezt

felhasznlva a rekurzis kplet I = O(n + ne = log n)-et szolgltat. 2 3 2 3 1 2 2 2 3 2 3 Az itt kapott fels becsls a log faktor nlkl aszimptotikusan elrhet. Edelsbrunner s Haussler 12] mutatta meg az albbit 4.3 llts: e  n esetn megadhat R3 -ban n klnbz pont s e darab ltaluk kifesztett sk, hogy az illeszkedsek szma I = (ne): Bizonyts: Kt kitr egyenesen legyen n=2 n=2 pont. Az ezek ltal kifesztett 2(n=2) = n sk kz l vegynk e darabot Most minden skra n=2 + 1 pont illeszkedik, gy I = (ne). 2 4.4 llts: n3 =8  e  n esetn megadhat R3-ban n klnbz pont s e, ltaluk kifesztett sk, hogy az illeszkedsek szma I = (ne = ): 2 3 Bizonyts: Az 1.12 ttelben megadott Erds-fle konstrukcit ksztsk p 0 0 n0  e0  n0 , el egy S skban p n = n=2 e = 2e=n ponttal s egyenessel. 0 Itt = = = 0 vagyis n =2 2  e  n =8 felttellel a konstrukci O(n e ) illeszkedst ad. Vegyk szre, hogy a konstrukciban minden egyenesre legalbb 2 pont

illeszkedik. Az S skon kvl vegynk fel egy L egyenest, ami nem prhuzamos egy S -beli egyenessel sem. Ezen legyen n=2 pont S egyenesei s L pontjai e0n=2 = e skot fesztenek ki. Ezzel minden S -beli illeszkeds n=2-szeres pontsk illeszkeds lett Az n pontnak s az ltaluk kifesztett e sknak az sszes illeszkedse I = O(n0 = e0 = ) n2 = O(e = n): 2 2 3 2 3 3 2 3 2 3 2 3 2 3 2 Itt rdemes megjegyezni, hogy az Rd-beli pont-hipersk illeszkedskre adott als becslsek egy msik problmnak is als becslst szolgltatnak. Rd-ben adott e hipersk a teret cellkra vgja. Egy cella de nilhat gy, hogy minden pontja minden hiperskra az ltala meghatrozott egyik fltrben van. A cellk d-dimenzis konvex politpok vagy polidrikus halmazok. Denci:Az e hipersk s a cellinak rendszert elrendezsnek hvjuk. 32 Denci: e hipersk elrendezsben megadott n cella bonyolultsga a cellk ((d ; 1)-dimenzis) lapszminak sszege. Cd(n e) a d-dimenziban e hiperskal s n

cellval elrhet maximlis bonyolultsg. 4.5 llts: Ha Id (n e) az Rd -ben adott n pont s e ltaluk kifesztett hipersk illeszkedseinek maximuma, akkor Cd(n 2e)  2Id(e n): Bizonyts: Legyen jPj = e jEj = n olyan, amire az illeszkedsek szma Id(e n). Tekintsk a dulis teret Itt pont kpe hipersk, hipersk kpe pont, az illeszkeds megmarad. Az, hogy E hiperskjait kifesztik a pontok, azaz minden hiperskra illeszkedik d an fggetlen pont azt jelenti, hogy a dulis trben minden pontra illeszkedik d hipersk, melyek normlisai linerisan fggetlenek. Minden p 2 E  dulis pont kr rjunk egy kis " sugar gmbt. Toljuk el a pontra illeszked dulis hiperskokat gy, hogy kt oldalrl rintsk a pont krli gmbt. A dulis hiperskok an fggetlensge miatt az eltolt hiperskok az " sugar gmbket rint politp lapjai. Ha " elg kicsi, akkor a klnbz p 2 E  pontokhoz tartoz rint politpok diszjunktak s cellt alkotnak P  elrendezsben.

Ekkor Cd(n 2e)  2Id(e n): 2 Az e hipersk elrendezsben adott n cella maximlis bonyolultsga nagyobb e hipersk s n metszspontjnak maximlis illeszkedseinl. 1990-ben Edelsbrunner, Guibas, Sharir s Welzl 7] beltta, hogy C (n e) = O(n = e = + n + e) = = I (n e). 2 2 3 2 3 2 4.b Megszor t sok az an alterekre Egy msik termszetes megszorts, hogy egy egyenesre legfeljebb konstans sok pont illeszkedjen, hiszen az ne-t megkzelt illeszkeds ppen akkor keletkezett, ha egy egyenesre sok pont illeszkedett. A Szemerdi-Trotter ttelbl knnyen levezethet egy az ilyen rendszerekre vonatkoz 4.6 Ttel: Legyen adott Rd -ben n klnbz pont halmaza P s e hipersk halmaza E , (d  2). Tegyk fel, hogy minden (d ; 2)-dimenzis an altrben legfeljebb K pont van valamely K  d ; 1 konstanssal. Ekkor t 2 K +1 n d; =d] esetn a legalbb t pont hiperskok szma  d  et = O end : ( +1 33 1) Bizonyts: Indukci d szerint. d = 2-re a Szemerdi-Trotter ttel szolgltatja

az lltst Ha Rd; -re mr tudjuk, lssuk be Rd-ben. Minden p adott ponthoz vegynk fel egy r nem illeszked hp hiperskot, ami nem prhuzamos egyetlen pontpr egyenesvel sem s vettsk erre a tbbi n ; 1 pontot. Az gy kapott vetletpontok halmaza legyen Pp. Itt jPpj  Kn;;  n=K (ha n  K ) Ep pedig legyen a pre illeszked adott hiperskok metszeteinek halmaza hp-skkal Ha h 2 E sk illeszkedik p-re s a h hp metszetben A darab vetletpont van, azt mondjuk, hogy a h hipersk a p ponbl A pontnak ltszik, (mint a 2.7 ttelben) Az indukcis felttel szerint a (d ; 1)-dimenzis hp hiperskban a legalbb t ; 1 pont (d ; 2) dimenzis hiperskok szma d; jPp jd; ept;  C (t ; 1)d  2Cd ntd  ha t ; 1 2 K + 1 (n=K ) d; = d; ], valamely csak a dimenzitl fgg C > 0 konstanssal. Egy hp-beli legalbb t ; 1 pont hipersk p-vel egytt t pont, ez mr kifeszt egy Rd-beli t pont hiperskot. Ha t 2 K + 1 K (K + 1)], hasznljuk a trivilis becslst: et  nd  (K (K + + 1))d nd=td .

Ha t 2 K (K +1) (n=K ) d; = d; +1] becsljk azokat a (p h) prokat, ahol p 2 P , h 2 E legalbb Kt pont s legalbb t ; 1 pontnak ltszik p-bl. Ezek szmt fellrl becsljk, ha h befutja az sszes p;-bl legalbb t ; 1 pontnak ltsz E -beli hiperskot. Ezt felrl becsli nC=2d n t 1 Egy-egy legalbb Kt pont hipersk viszont minden pontjbl minimum t ponnak ltszik, mert egy pontjbl a tbbi legalbb  (Kt ; 1) pont legalbb Kt; pontnak ltszik. K; Eszerint ekkor d; d n n n d d eKt  t (C=2 ) td = (C=2 ) td : 1 1 1 1 1 1 ( +1 2) ( 1) +1 ( 2) ( 1) d d 1 1 1 +1 Teht egy tetszleges t helyett K tbbszrst vve et  et=K  C=(2K )d tn+1 , ahogy kvntuk. Ha t 2 (n=K ) d; = d; + 1 n d; =d], akkor  d; =d d et = O(n=t)  O(n=t) n t = O(nd =td ): Vegyk ugyanis egyenknt a legalbb t pont hiperskokat. $sszesen legfeljebb   d n O ((n=K ) d; =d)d = O(n =d ) ilyen hipersk van. Az i-edik hipersk legalbb t ; K (i ; 1) pontot Pe tartalmaz, mert minden

korbbival legfeljebb K metszspontja van. gy n  i (i ; K (i ; ; 1))  tet ; Kn =d > tet ; Kn ebbl et  (K + 1)n=t. 2 2 ( 2) ( 1) ( 1) ( 1) +1 1 ( 1) +1 t =1 2 34 d d Kimondhat itt is az 1.2 s 35 llts megfelelje: 4.7 llts: Legyen adott Rd -ben n pont s egy e hipersk Minden (d ; 2)- dimenzis an altrben legfeljebb K pont van valamely K  d ; 1 konstanssal. Ekkor az illeszkedsek I szmra egyszerre teljesl (1) I = O(nk= k ek= k + n + e) ( +1) ( +1) n =k  e  nk eseten I = O(nk= k ek= k ) (2) 1 ( +1)  ( +1)  k et = O tnk + nt  ha t 2 d n]: (3) +1 Bizonyts: (1) ) (2). n =k  e  nk esetn n = nk= k n = k e = ek= k e = k  ek= k nk= k . 1 ( +1) ( +1) 1 ( +1) ( +1) 1 ( +1) ( +1)  nk=(k+1) ek=(k+1) s   (2) ) (3): Elszr azt ltjuk be, hogy 2  t  Dn k; =k esetn et = O tn+1 , (D > 1). Legyen C > 0 olyan, hogy n =k  e  nk esetn I < Cnk=k ek=k teljesljn. Indirekt tegyk fel hogy tallhat e = C k Dk

nk =tk legalbb t pont hipersk. Ezek illeszkedseinek szma I  et = C k Dk nt Msrszt t 2 CD Cn k; =k] esetn n =k  e  nk s I  Cnk=k ek=k;  = Ck Dk nk =tk kvetkezik, ellentmonds. t 2 2 CD ; 1] esetn pedig et  nk = O tn+1 p ;  Most azt ltjuk be, hogy t 2 2Kn n] esetn et = O nt . Tekintsk az sszes legalbb t pont hiperskot. Az els k darab hipersk (k 2 1 et]) legalbb t +(t ; K )+(t ; 2K )+ +(t ; (j +1)K ) adott pontot fed le, hiszen indukcival a k-adik maximum (k ; 1)K adott pontban metsz kisebb index egyeneseket s a szummba nem kerlhetnek negatv tagok, mert t + ( t ; K ) + +1  t t; K > p Kn2 > K = n. gy az et egyenes ltal lefedett sszes pontra: n  t + (t ; K ) + + + (t ; etK + 1) > tet=2K amibl et < 2Kn=t. ( 1) k 1 +1 +1 +1 +1 ( 1) k 1 +1 +1 +1 +1 +1 k k +1 k k ( 1) 2 2 2 (3) ) (1): Tudjuk, hogy ha t 2 k Dn k; =k ] esetn et  C tn+1 . Becsljk fellrl az illeszkedsek szmt. Legyen l a legkisebb olyan

termszetes szm, hogy k C k lkn  e: ( k 1) k +1  +1  +1) Ekkor l = O ne1 (( +1)  s a legfeljebb Dn =k pont hiperskok sszes illeszkedseit fellrl becsli ( ;1) Z Dn( ;1) DnX k n nk dt = k=k k=k Ke + Kle +  Ke + O ( n e ) + k tk l t l t k= k 1 = k k =k k +1 +1 =k +1 +1 = 35 Ke + 1=knk ( l1k ; D1k n )  Ke + O(nk= k ek= k ): ( +1) ( +1) A Dn k; =k -nl tbb pont hiperskok szma legfeljebb DC+1 n =k . Illeszkedjen az P egyes grbkre a(i)  Dn k; =k pont. Ezen grbk sszes illeszkedse I 0 = = i a(i). Ha egyenknt rakjuk le az grbket a skra, akkor a j -edik legalbb a(j ) ; K (j ; 1) jabb pontot fed le, mert az els (jP ; 1)-gyel legfeljebb K (j ; 1) P PDpn metszspontja van. n  i(a(i) ; K (i ; 1))  i a(i) ; i K (i ; 1)  P  i a(i) ; O(n). Ebbl I 0 = O(n) ( 1) k ( 1 1) =1 2 A tbb dimenzis Beck-ttel mdszereit alkalmaztuk, a Beck ttel pedig a lehet legjobb becslst adja a kifesztett hiperskok szmra. Az illeszkedsek szmra

viszont ismert a fentinl jobb fels becsls is, de az lessgrl mg ott sem ismert eredmny. Az illeszkedsek szmllst az nehezti, hogy hrom vagy tbb dimenziban kt hipersk metszete nem foglalhat egy vges tartomnyba. Ezt kszbli ki a K.L Clarksontl 6] szrmaz, vletlen mintkat hasznl 4.8 Ttel: Legyen S hiperskok vges halmaza Rd -ben, R S vletlen minta S -bl. Ekkor 1=2-nl nagyobb valsz sggel az R elrendezs ltal megadott cellk hromszgelsben minden ltalnostott szimplexet sO(log r=r) darab S -beli hipersk metsz. (Ahol jS j = s jRj = r metszsnek azt nevezzk, hogy a 2 sk metszete a szimplex relatv belsejvel nem res). A vges sok hipersk ltal de nilt cellk hromszgelse magyarzatra szorul, mivel egy elrendezs celli kzt nem-korltosak is vannak, politpokra darabolni nem lehet ket. Denci: e darab hipersk elrendezsnek cellira a hromszgelst gy rt- jk, hogy a korltos cellk szimplexfelbontst vesszk. A nem-korltos

cellk esetben dimenzi szerint rekurzve de niljuk a hromszgels ltalnostott szimplexeit. 1 dimenziban egy flegyenes ltalnostott szimplex A cellk nemkorltos (1-dimenzis) leit is #vgtelen tvoli" cscsnak tekintjk Ha van a cellnak cscsa, akkor a cella hatrnak hromszgelsbl minden ltalnostott szimplexre egy csccsal vett konvex burkok az ltalnostott szimplexek. Ha a cellnak nincs cscsa, akkor elll P + L alakban, ahol L az Rd egy lineris altere, P pedig egy kisebb dimenzis cella, aminek mr van cscsa. Ilyenkor a cella hromszgelsnek ltalnostott szimplexei K + L alakban llnak el, ahol K a P cella egy ltalnostott szimplexe. 36 L P Minden cella felbonthat diszjunkt belsej ltalnostott szimplexek unijra. Egy valszn sgi lemmt hasznlunk fel. Elbb azonban clszer bevezetni az albbi jellseket: P (t fggetlen  valszn sg esemnybl j ; t bj (j  t )t;:= j kvetkezik be ) = j  (t ; ) : A P (Rd) halmazcsaldra s B

Rd tartomnyra jellje #(A B ) = = jfa 2 A : a B 6= gj. 4.9 Lemma: Legyenek S F R N P ( d) halmazcsaldok, jS j = s i l 2 x konstansok. Tekintsk lekpezseknek egy vk : S i 7! F (k 2 1 l]) rendszert, azaz olyan lekpezseket, melyek S -beli rendezett i-esekhez rendelnek F -beli halmazokat. Legyen R vletlen minta S -bl, jRj = r (R elemei nem felttlen klnbzek). FR := fvk (Ri ) : k 2 1 n]g azaz FR legyen az R minta ltal de nilt sszes F -beli halmaz. Ekkor m 2 N-re s 0    1-re, ahol m  (r ; i), teljesl P (9A 2 FR : #(A R)  m #(A S ) < s)  O(ri ) X j m b(j  r ; i ): 4.10 Kvetkezmny: P (9A 2 FR : #(A R) = 0 #(A S ) > s)  O(ri )(1 ; )r;i minden x i-re s n-re. Alkalmas  = O(log r=r)-rel ez a valszn sg 1=2-nl kisebb. Ha S halmaznak a 4.8 ttelbeli skok halmazt veszk, F pedig az R S vletlen minta elrendezsben a cellk ltalnostott szimplexei, akkor ez ppen azt jelenti, hogy 1=2-nl nagyobb valszn sggel minden

ltalnostott szimplexet legfeljebb s sk metsz. 37 Bizonyts (4.10 Kvetkezmny): Alkalmazva az elz ttelt m = 0 ;  P esetben a fels korltban jm r;j i j (1 ; )r;i;j = (1 ; )r;i .  = c log r=r vlasztssal alkalmas c konstanssal ez O(ri (1 ; log r=r)r;i  1=rr ! 0 (r ! 1): Megadhat c gy, hogy ez mindig kisebb legyen 1=2-nl. Bizonyts (4.9 Lemma): A valszn sgszmtsbl csak annyit hasz- nlunk fel, hogy valamely X Y esemnyprra P (X ^ Y )  P (X ) + P (Y ) s P (X ^ Y )  P (X jY ). Jelljk R elemeit 1 r]-beli szmokkal. Ezzel 2 1 r]i vektorra rtelmes vk ( ) 2 FR (k 2 1 l]) halmaz is, ez R vlasztstl fgg valszn sgi vltoz. Itt P (9A 2 Fk : #(A R)  m #(A S ) > s) = = P (9 2 1 r]i9k 2 1 l] : #(vk ( ) R)  m #(vk( ) S ) > s) mert a kt esemny azonos. Ez utbbit fellrl becsli X r21r] k21l] P (#(vk( ) R)  m #(vk ( ) S ) > s)  i  lj 1 r]ij max  21r] k21l] i P (#(vk ( ) R)  m j#(vk( ) S ) > s)

elg teht P (#(vk( ) r)  m j#(vk( ) S ) > s)-et becslni minden -ra s k 2 1 l]-re. Jellje R0 a -beli szmokkal indexelt mintahalmazokat. Mivel a -beli szmokkal indexelt mintk fggetlenek azoktl, amelyek nem ilyenek, annak valszn sge, hogy egy (R ; R0)-beli halmaz metszi vk ( )-t pontosan #(vk ( ) S )=s annak valszn sge pedig, hogy #(vk( ) R) = j ppen b(j  r ; i #(vk( ) S )=s). VglPannak valszn sge, hogy a vk ( )-t metsz mintk szma legfeljebb m pont jm b(j  r ; i #(vk( ) S )=s). Az olyan -kra, melyekre #(vk ( ) S )=s > s, b(j  r ; i ) > b(j  r ; i #(vk( ) S )=s) mivel b(j  r ; i )-nak a szerinti derivltja negatv, ha > j=(r ; i) s j=(r ; ; i)  m=(r ; i)   < #(vk0 ( ) S )=s. gy aztn P (#(vk ( ) R)  m j#(vk ( ) S ) > s)  X j m b(j  r ; i ): 2 4.11 Megjegyzs: Ha kiktjk, hogy R minden eleme legyen diszjunkt, ak- kor is igaz a fenti llts, mert r  s esetn annak valszn sge, hogy R kt eleme

egybeessen nagyon kicsi s P (X ) 7! 1 P (Y ) > c > 0 esetn P (Y jX ) 7! P (Y ). 38 Bizonyts (4.8 ttel): Alkalmazzuk az elbbi lemmt az imnti kvetkezmny szerint vlasztott m = 0-val s  = O(log r=r)-rel Legyen S = S i = = d(d + 1). A v lekpezs-csaldot gy fogjuk megadni, hogy minden olyan tartomny belseje, ami az R elrendezs cellinak hromszgelsben van, FR eleme legyen. Ekkor a lemma kvetkezmnye ppen a kvnt lltst szolgltatja Indexeljk a v lekpezseket vmd0 -val, ahol m 2 0 d] d0 2 2 d]. Ezzel a v lekpezsek szma d(d + 1). A klnbzen indexelt lekpezsek rendre a hromszgels klnbz fajta ltalnostott szimplexeit adjk meg d0 < d-re vmd0 az elfajul FR elrendezsek esetben jut szerephez. Ha valahol nem akarjuk rtelmezni v lekpezst, v kpezzen az reshalmazra v d kpezzen a hromszgels szimplexeinek belsejre. v argumentumt osszuk d +1 darab S d-re. Ha mindegyik hipersk d-es metszete egy-egy pont, legyen v(~s) az

ltaluk meghatrozott szimplex klnben az reshalmaz. vmd (0 < m) az olyan ltalnostott szimlexeket de nilja, melyeknek van valdi cscsa s m darab #vgtelen tvoli" cscsa van. Az els (d + 1 ; m) d argumentum ltal meghatrozott d + 1 ; m pont (ha ezek pontok) s a kvetkez m (d ; 1) ltal megadott m irny ltal kifesztett ltalnostott szimplex legyen vmd(~s). vmd0  (d0 < d) az elfajul cellk hromszgeit de nilja, ahol a cella L + P felbontsban L egy d0 dimenzis altr. Az argumentum els d0 hiperskja de nilja L irnyt, a tbbi pedig a fent lert mdon megadja L? -ban a P ltalnostott szimplexeit. Ezzel az R elrendezs hromszgfelbontsnak minden ltalnostott szimplexe szerepel FR-ben. 0 2 4.12 Segdttel: Rd -ben r darab hipersk elrendezsnek van hromsz- gelse, ahol az ltalnostott szimplexek szma O(rd ). Bizonyts: Dimenzi szerinti indukcival. Az llts d = 1-re nyilvnval d > 1-re pedig ksztsk el az r hiperskon a

tbbi r ; 1 hipersk metszetnek hromszgelst O(rd; ) ltalnostott szimplexszel. Az r hipersk elrendezsnek cellit gy hromszgeljk, hogy a cella hatrnak hromszgelsbl minden szimplexet egy ponttal ktnk ssze. gy minden ltalnostott szimplexnek egy lapja valamely hipersk hromszgelsbl val, s egy ilyen (d ; 1)-dimenzis ltalnostott szimplex kt ddimenzis ltalnostott szimplexet hatrol. Teht az ltalnostott szimplexek szmt felkrl becsli 2rO(rd; ) = O(rd ). 2 1 1 Ezen elksztsek utn kimondhatjuk Edelsbrunner-Guibas-Sharir ttelt pontok s skok illeszkedsrl hrom dimenziban: 39 4.13 Ttel: Legyen adott n klnbz pont s e klnbz sk R3 -ben, a pontok kzt nincs k kollineris (k x). Ekkor az illeszkedsek szma: I = O(n = ; e =  + e + n log e): 3 5 4 5+2 A bizonyts egy algoritmusra pl, amely az illeszkedseket szmllja az "Oszd-meg-s-uralkodj" elv szerint. A kiszmtand rszfeladatokat egy vletlen

mintavtel szerint vlasztjuk ki gyelembe vve a tr dulist is, ahol pont kpe sk, sk kpe pont, a tartalmazs megfordul, de az illeszkeds megmarad. Bizonyts: Legyen P a ponthalmaz, E pedig a skhalmaz. P  a dulis skok halmaza, E  a dulis pontok halmaza. Vlasszunk ki egy r elem vleteln mintt a dulis skok P  halmazbl, (r 2 N ksbb megadand nagy szm). A minta elemei a Rd teret konvex polidrikus halmazokra bontjk A polidrikus halmazok felbonthatk ltalnostott szimplexekre. Rgztsnk egy szimplex-felbontst a vletlen minthoz A 4.12 lemma szerint van olyan felbonts, amelyben az ltalnostott szimplexek szma O(r ) Minden T szimplexre elksztnk egy rszproblmt. Ebben ET jelli azon s 2 E skokat, melyekre az s dulis sk T -ben van, s PT azon p 2 P pontokat, melyekre p metszi T -t. A rszproblma szmolja a PT s ET kztti illeszkedseket, IT -t A Clarksontl szrmaz 4.8 ttel s a 410 kvetkezmny szeint pozitv valszn sggel egy minthoz tartoz

minden T szimplexet legfeljebb (cn=r) log r dulis sk metsz, valamely c > 0 konstanssal. Rgztsnk egy ilyen mintt Az #Oszd meg-s-uralkodj" elv szerint gy osztjuk tovbb a rszfeladatokat egszen addig, mg nT  eT nem teljesl (nT = jPT j eT = jET j). Ekkor kiszmtjuk a rszproblmt Ha a rszproblmban egy pont csak egy skra illeszkedik, az egy illeszkedst ad, ez nT pontra legfeljebb nT illeszkeds. Nzzk azokat a pontokat, amelyek tbb skra illeszkednek. Ezek rajta vannak kt ET -beli sk metszsvonaln Egy metszsvonalon legfeljebb k pont van, egy skot legfeljebb eT ; 1 msik metsz, ez skonknt keT -nl kevesebb illeszkeds, sszesen keT . A rszproblmban teht IT  nT + keT  2knT . Legyen BT = fp 2 P : p T = g az sszes olyan pont halmaza, melyek dulisai elkerlik T -t. bT = jBT j Ekkor a p 2 BT dulis sk vagy minden sT 2 ET T pont fltt van vagy mindegyik alatt. A dualits megtartja az alatta-fltte relcit, ezrt p 2 BT pont vagy minden sT 2

ET sk fltt van vagy mindegyik alatt. Legyen UT  UT; R az a kt konvex halmaz, melynek elemei minden ET -beli sk fltt, ill. vannak Szmoljuk az illeszkedseket BT s ET kzt. Ha p 2 BT pontosan egy ET -beli skra illeszkedik, az egy illeszkeds, sszesen bT . Ha p tbb skra is illeszkedik, 3 2 2 2 2 + 3 40 rajta van UT vagy UT; valamely ln. Vettsk UT hatrt egy vzszintes skra Tekintsk lnek a ET -beli skprok hatrra es rszt. (Megengednk tbbszrs leket is) Az lek egy skgrfot adnak Tudjuk, hogy ez a skgrf legfeljebb eT tartomnyra bontja a skot. Az Euler-fle poliderttelt alkalmazva a dulis skgrfra azt kapjuk, hogy leinek szma kisebb 3eT -nl. Egy len legfeljebb k pont lehet, ezzel 3keT -nl kevesebb illeszkedst kaphatunk. Ugyangy szmolva UT; -on, sszesen legfeljebb 2nT + 6keT illeszkedst kaphatunk. Az eljrs vgn gy szmoljuk ssze az illeszkedseket, hogy rekurzve kiszmtjuk az egyes szimplexek belsejre s hozzadjuk a

megfelel T -hez tartoz BT illeszkedseit. Teht az albbi rekurzv formult kapjuk: + + I (n e) =  O (n) P ha n  e  N I (n e ) + O(n + m) ha n < e i i i 2 2 =1 ahol N = OP (r ) az r darab sk felbontsbl szrmaz szimplexek szma, s gy persze n = Ni ei  e. Az I (n e)-re fels becslst adunk a rekurzv formula segtsgvel. Azt szeretnnk beltni, hogy I (n e) = O(n = ; e =  + e + n log e): 3 =1 3 5 4 5+2 Ehhez rgztsk  2 (0 1=12)-t. r legyen -tl fgg konstans a rekurziban A rekurzis kplet O(ei) adalka a rekurzi fjnak egy szintjn legfeljebb O(e). Mivel az eljrs log n lpsben vget r, ez az egsz rekurziban O(e log n) lesz. Ha n  e , akkor I = O(n) , kszen vagyunk. Ekkor I  Cn Ha n < e az indukci szerint 2 2 I N X i=1 C (ni = ;ei = 3 5  + e log n + n ] + O(n): i i 4 5+2 Clarkson 4.8 ttele szerint ni  (cn=r) log r minden i-re, ezrt N X i=1 s gy IC  N X i=1 O(ni )  c (Nc=r) log rn 1 ni = ; e4i =5+2 3 5 !

+ c Nc r log r + c ]n 1 2 alkalmas c  c > 0 konstansokkal. Itt a msodik tagban n becslhet n = n = ;n =   n = ;e = ; ;vel: 1 2 3 5 2 5+ 3 5 41 4 5 2 ni  cn=r log r miatt, a Hlder-fle egyenltlensg alapjn, valamint N = O(r ) miatt N N X X = ; =  = ;  = ;  ni ei  (cr= log r) n ei =   3 3 5 4 5+2 3 5 i=1 4 5+2 3 5 i  (cr= log r) = ; n3=5; N 1=5;2 3 5  N !4=5+2 X i=1 ei  log = ; r n = ;e =  r = ; I  (Cc log r  r + c r log r + c )n = ; e = : Vlasszuk r-et olyan nagynak, hogy c 3r85; r  legyen. Vlaszuk a C konstans rtkt 2c r log r + c -nak. Ezzel I  C (n = ;e = ):  c3 3 5 3 5 3 5 3 4 4 8 3 2 4 5+2 8 2 2 log =  3 5 4 5+2 1 2  2 3 5 4 5+2 2 A legjobb als becsls messze van a 4.13 ttel ltal sugallt I = O(n = e = + + n + e) korlttl. Erickson 16] konsrtukcija az Erds 2-dimenzis les konstrukcijhoz hasonlan az Euler-fle fggvny elemi tulajdonsgait hasznlja s az R kockarcsn ad meg

skokat. 3 5 4 5 3 4.14 llts: Brmely n e 2 N-re, melyre e1=3  n  e, tallhat n klnbz pont s klnbz e sk R -ben, hogy a pontok kzt nincs 3 kollineris s az illeszkedsek szma: I = (n = e = ) 3 1 2 5 6 Bizonyts: A dulis problmra adunk konstrukcit. Azaz megadunk n klnbz pontot s e skot (n =  e < n), ahol nem illeszkedik hrom sk egy egyenesre az illeszkedsek szma (n = e = ). Tegyk fel, hogy 8jn = 2 N.5 Az n pont halmaza legyen 1 n = ] R s l = b(e=n = ) = c 2 N. De niljuk a h(a b c r s)-t, mint az (a b c), (a + r b + s c), (a + r b c + r ; s) pontokra illeszked skot. A skok halmaza legyen 1 3 5 6 1 2 1 3 1 3 3 H= 5 3 1 3 1 4 fHrs jr 2 1 l] s 2 1 r]: lnko(r s) = 1g Ez csak konstansszoros eltrst okoz, mint azt az 1.12 ttelben lthattuk 42 (a+r,b,c+r-s) z y (a+r,b+s,c) x (a,b,c) ahol Hrs = fh(a b c r s)ja 2 1 r] b 2 1 s] c 2 1 n = =2]g: Mivel lnko(r s) = 1, gy r s (r ; s) pronknt relatv

primek, ezrt klnbz r s-re Hrs skjai klnbz irnyak. Hrs elemei pedig ismt csak klnbzek Eszerint  =  l l = X X X n n r r 2(r)  jH j = r s 2  2 r r s 2 r 1 3 1 3 =1 1 1 3 =1 ] r s) = 1 l 1=3 X lnko( n = 4 r r = n O(l ) = O(e): Ha H -ban lenne hrom egy egyenesre illeszked sk, akkor a skok metszete a (x = 0) skkal hrom egy pontra illeszked egyenest tartalmazna. A konstrukcinkban minden sknak van (1 1 1)-re illeszked eltoltja, ezrt feltehetjk, hogy a hrom sk h(1 1 1 r s) alak, valamely r s prra. A h(1 1 1 r s) (x = 0) metszet az (0 1;s=r 1) (0 1 s=r) pontra illeszked egyenes Ezek mind klnbzek s egy parabolt rintenek, ezrt nem lehet hromnak kzs pontja. Az illeszkedsek szmt annak a tnynek a felhasznlsval becslhetjk, hogy k 2 1 n = =2r] esetn h(a b c r s) (x = a + ki) metszet legalbb k rcspontot tartalmaz. Ebbl 3 = rc  =   =  bn1X n n = j 1 n ] h(a b c r s)j  k > 1=2 2r  1=2 2r ; 1

 k  3 1 3 4 =1 1 3 = 2 1 3 1 3 3 2 1 3 2 =1 l = X I  n2 r r 1 3 =1 X s 2 1r] rs) = 1  s n= 2 2r 1 3 2  l n= X 4 r 1 3 =1 lnko( X s 2 1r] rs) = 1 lnko( 43 s n = ; 2n =  2 4r 2 3 1 3 (n)  l X (r);O(n = ) 2 3 l X r (r)  (nl );O(n = l )  (n = e = );O(n = e = ): r=1 r=1 Teht n1=3  e  n esetn I = 2 2 3 3 5 6 1 2 5 12 3 4 (n = e = ): 5 6 1 2 2 Megjegyzs: Ha n  e, akkor a ktdimenzis esetbl szrmaz trivilis als becsls az ismert legjobb. Egy S skon legyen n pont s e egyenes (n = e = + + n + e) illeszkedssel (1.12-nek megfelelen) Minden egyenesre illessznk egy S -re merleges skot. Mozgassunk el minden pontot az S skbl S ? irnyba gy, hogy ne legyen kztk hrom kollineris. Ekkor I = (n = e = + n + e) 2 3 2 3 2 3 2 3 4.c Egy cell ban lv pontok Fontos alkalmazsai vannak annak a specilis esetnek is, melyben az Rdben adott e hipersk egy zrt celljban adott n pont. Az illeszkedsek csak a cella hatrn

jhetnek ltre. Ebben az esetben is elfordulhatna, hogy minden pont a cella hatrnak egy egyenesn van, ami ne illeszkedst adna. Bizonyos megszortsokkal itt is elrhet jobb eredmny. Edelsbrunner s Sharir 13] bizonytotta a ngydimenzis esetre a kvetkezt. 4.15Ttel: Legyen adott R4-ben n pont P halmaza s e hipersk E halmaza gy, hogy 1. minden hipersknak egyik zrt flterben van az sszes pont, 2. nincs hrom kollineris pont P -ben, 3. nincs hrom E -beli hipersk, melyek metszete 2-dimenzis an altr Ekkor a P s E kztt fellp illeszkedsek szma I = O(n = e = + n + e): 2 3 2 3 A ttel bizonytsa ezttal is vletlen mdszereket hasznl. Clarkson s Shor 8] valszn sgi lemmihoz kiegsztjk a 4.10 eltt bevezetett jellseket S F P (Rd) halmazcsaldok. Vezessk be a v : F 7! S b (b 2 N x) fggvnyeket fv(F )g a v(F ) rendezett b-es elemeinek halmaza. n : F 7! N multiplicitsfggvny minden F 2 F -re megadja F azon F -beli pldnyainak szmt, amelyekre v(F

) is megegyezik.6 6 F multihalmaz 44 Jellje FR azokat a F 2 F halmazokat, melyre v(F ) 2 Rb. Vgl pedig legyen j FR = fF 2 FR : #(F S ) = j g, (j 2 ). N 4.16 Lemma: Legyen R S vletlen minta, melynek r klnbz elembl     X s ; b ; #(F S ) s M jF j]: #(F S )  R r;b;1 r F 2F ll. Ekkor 1 S Bizonyts: Minden F 2 FS -re legyen IF az fF 2 FR1 g esemnynek az indiktorfggvnye. Ezzel " M jFRj] = M 1 X F 2F # IF = S X F 2F M IF ] = S X P (F 2 FR): 1 F 2F S Vegyk szre, hogy egy F 2 FS halmazra F 2 FR teljesl, ha #(F R) = = 1 fv(F )g R: Eszerint a P (F 2 FR) valszn sget alulrl becslhetjk gy, hogy e felttelnek megfelel r elem mintk szmt osztjuk az sszes lehetsges minta szmval. A felttelnek eleget tesz R, ha #(F S )-bl kivlasztunk egy elemet, bevlasztjuk az F -et de nil jfv(F )gj elemet s tovbbi r ; jfv(F )gj ; 1 elemet vlasztunk S fennmarad legalbb s ; iF ; 1 elembl.     s ; jfv (F )gj ; #(F S ) P (F 2 FR)

 #(F S ) r ; jfv(F )gj ; 1 = sr : Vgl jfv(F )gj  b miatt     s ; jfv(F )gj ; #(F S )  s ; b ; #(F S ) : r ; jfv(F )gj ; 1 r;b;1 1 1 1 2 Legyen g konkv, monoton nv vals fggvny. Ezzel igaz lesz az albbi 4.17 Ttel: A bevezetett jellsekkel 2 3   M4 g(#(F S ))5  g s ;r ;r ;b 1 MjFjFRj j] jFRj: R F 2F 0 X 1 0 0 R Bizonyts: Most IF legyen az fF 2 FR0 g esemnynek az indiktorfggvnye. Ekkor 2 M4 X F 2F 0 R 3 g(#(F S ))5 = M " X F 2F # IF g(#(F S )) = S X F 2F S 45 M IF g(#(F S ))] = X F 2F   0  P (F 2 FR)g(#(F S ))  M jFRj g 0 S X F 2F ! P (F 2 FR)g(#(F S ))=jFRj S 0 P 0 a Jensen-egyenltlensg szerint s mert M jFRj] = F 2F P (F 2 FR). Hasznlhatjuk a 4.16 lemmt g argumentumnak becslsben,     X X s ; jfv (F )gj ; #(F S ) s  P (F 2 FR)#(F S ) = #(F S ) = r;b;1 r F 2F F 2F     s ;r+1 X s ; b ; #(F S ) s = s ; r + 1 M jF j :  #( F S ) = R r ; b F 2F r;b r r;b Behelyettestve a

ttel lltst kapjuk. 0 0 S 0 S S 1 S 2 Az illeszkedseket most is az "Oszd-meg-s uralkodj" elve alapjn szmoljuk. A rszproblmk valamelyikt viszont mr meg kell tudnunk oldani. Trivilis eszkz erre a 3.2 Kvri, TSs, Turn ttel, ami a 2,3 felttelek szerint azt adn, hogy I = O(ne = + e) I = O(n + n = e). Az 1 felttel azonban jobb becslst tesz lehetv. 2 3 2 3 4.18 Lemma: A 415 ttel 1-3, feltteleivel p I = O(n e + e) p I = O(n + ne): Bizonyts: A dulis trben a 2., s a 3, felttel p felcserldik, mg az 1. felttel ndulis. Ezrt elg beltni, hogy I = O(n + ne) Legyen T a E -beli hiperskok ltal hatrolt zrt politp, amely tartalmazza a P ponthalmazt. Feltehetjk, hogy az orig T belsejben van Szmoljuk az illeszkedseket pontonknt. Ha egy p 2 P pont T egy (3-dimenzis) lapjnak belsejben van, akkor egy illeszkedst ad. Ha egy p 2 P pont T egy 2-dimenzis lapjn van, akkor a 3 felttel miatt kt illeszkedst ad. gy az eddig

szmolt pontok sszesen O(n) illeszkedst adnak. A 2. felttel miatt T egy 2-dimenzis lapjn legfeljebb 2 adott pont lehet T egy cscsban egy pont lehet. Egy politpot egyszer nek neveznk, ha minden i-dimenzis lapjt d ; i darab hiperlap tartalmazza, ahol i 2 0 d ; 1]. Az Euler formult ltalnost DehnSommerville relcinak kvetkezmnye, hogy egy egyszer politpban a cscsok s lek szma O(ebd= c), itt O(e ) 10]. Eszerint a cscsban lv s l belsejben lv pontok illeszkedseinek szma O(e ), ha T egyszer . Ha T nem egyszer , akkor toljuk el E minden olyan hiperskjt, ami T -nek csak cscst vagy lt tartalmazza, a T belsejben lv orig fel "-nal gy, hogy 2 2 2 46 az j politpot egy lapban messe. Majd mozgassuk a laphiperskokat gy, hogy minden cscsra csak hrom laphipersk illeszkedjen. Ezzel az l-hipersk s cscshipersk illeszkedsek szma nem cskkent, s most mr O(e ) p Eddig az illeszkedsek szmra O(n + e )-es korltot kaptunk. e < n esep

p tn ez O(n). Egybknt vgjuk az E halmazt d e= n e darab n elem rszre. p 0 Mindegyik rszben p O(n + ( n) ) = O(n) illeszkedst kapunk P s E kztt. $sszegezve ez O( ne). 2 2 2 2 Bizonyts (4.15 ttel): T most is az E -beli hiperskok ltal hatrolt, P -t tartalmaz zrt cella az orig T belsejben van. A 4.17 Ttelt szeretnnk alkalmazni Legyen S = E , R egy r elem vletlen minta a hiperskok halmazbl. De niljuk az F tartomnyokat. TR legyen az R minta hiperskjainak T politpot tartalmaz cellja. Hromszgeljk TR-t a kvetkezkppen: Jelljnk ki minden 2-dimenziss lapon egy cscsot s minden (3-dimenzis) lapon egy cscsot. A 2-dimenzis lapokat hromszgeljk gy, hogy minden cscsukat sszektjk a kijellt csccsal A (3-dimenzis) lapokat pedig gy, hogy a 2-dimenzis lapjaik minden hromszgnek a konvex burkt vesszk a kijellt csccsal. Vgl ezek a 3-dimenzis szimplexek az origval kpzett konvex burkai T hromszgelst adjk. A hromszgels

szimplexeinek szma legyen k, ezt fellrl becsli T l, 2dimenzis lap illeszkedseinek szma. Az egy lre illeszked 2-lapok szma kisebb az lre illeszked lapok szmnl errl pedig mr tudjuk, hogy az sszes lre legfeljebb O(e ). A hromszgelsben teht O(r ) szimplex van F legyen ezen szimplexek unija az sszes lehetsges R mintra. Adjuk meg a v fggvnyt, v : F 7! S . TR egy szimplext R elemeivel adjuk meg. Elg a szimplex origval szemkzti lapjt megadni Ez TR egy lapjn van v(F ) legyen a lap hiperskja. v(F )  : : : v(F ) kimetszi a hiperskbl TR megfelel lapjnak kijellt ponjt, lF -et v(F ) kimetszi v(F ) -bl az lF -fel szembeni 2-dimenzis lap 2-dimenzis an altert. Ebbl v(F )  v(F ) kimetszi a megfelel 2-lap kijellt cscst v(F )  : : : v(F ) pedig kimetszi a 2-lapbl az ezzel szemkzti l egyenest s annak kt cscst. Adott R mintra az i-edik szimplex belsejben lv pontok P szma legyen ni, a szimplex belsejt metsz hiperskok szma ei, (i 2 1

k], ki P ni  n). A 4.18plemma szerint a szimplexek belsejben lv illeszkedsek szmap ki O(ei + + ni ei). Alkalmazva a 417 ttelt ennek a vrhat rtke O(n e=r + ke=r) lesz, ahol k = O(r ). Ugyanis 1 multiplicitssal s g = id vlasztssal 2 2 10 1 2 4 5 1 6 8 7 10 =1 =1 2 M " k X i=1 #    ;1  O(ei) = O e r;;r 10 M jFRj = O(kn=r): 1 47 n(F ) = jF Pjmultiplicitssal s g : x 7! px-szel M " k X i=1 p # O(ni ei) = O r ! e ; r ; 1 jF jM jF j] = O(npe=r): R r ; 10 R 0 1 Van teht egy olyan R minta, melyre ez a mennyisg nem nagyobb a vrhat rtknl. Ezen kvl szmolnunk kell a szimplexek hatrn, azaz R hiperskjain lv illeszkedseket. Legyen H 2 R s PH = H P PH konvex burka egy legfeljebb 3-dimenzis politp a lapjainak s leinek szma az Euler-ttel szerint O(jPH j). A 2. s 3 felttel miatt a lapot alkot hiperskok O(jPH j) illeszkedst adnak A politpot csak lben vagy cscsban metsz hiperskok O(e) illeszkedst adnak.

Pr Eztpsszegezve R hiperskjaira: i O(O(jPH j) + n) = O(I (n r) + er) = O(n + + r n + e) a 4.18 lemma szerint p Eddigpazt tudjuk az sszes illeszkedsek szmrl, hogy I = O ( n e=r + p = = + er + r n + n). Most e  n  e esetn legyen r =p dn e e Ekkor I = O(n = e = + n + n = e = ) = O(n = e = + n). Ha pedig e > n vagy n > e , akkor a 4.18 lemmbl I = O(n + m) =1 2 2 3 2 3 7 6 1 3 2 3 1 3 2 3 2 3 2 2 A fenti ttel 1. felttele, mely szerint minden pontnak a hiperskok elrendezsnek egy celljban kell lennie, ersnek t nik mgsem ismert j als becsls I -re ebben a specilis esetben. A ttellel ennek ellenre lehetett javtani R -beli tvolsgproblmk becslsein. Egy egyszer eljrs adja az Edelsbrunnertl s Sharirl 13] szrmaz ttelt. 3 4.19 Ttel: Legyen adott R3-ban n diszjunkt pont s e gmb7 s sk gy, hogy minden skra s gmbre a P az ltala meghatrozott egyik zrt fltrben van. nincs hrom sk, egyenes, amelyek metszete egy kr vagy egyenes

lenne. Ekkor a ltrejv illeszkedsek szma I = O(n = e = + n + e): 2 3 2 3 Bizonyts: Hasznljuk az elz 4.15 ttelt A p = (p1  p2  p3 ) 2 R3 pont helyett vegyk a p0 = (p  p  p  p + p + p ) 2 R felemelt pontot a g = = f~x 2 R : x = x + x + x g paraboloidon. 4 7 4 2 1 2 2 2 3 1 2 3 2 1 rtsd: gmbfelszn 48 2 2 3 4 Egy gmb vagy sk kpe a pontonknti felemeltjkre illeszked hipersk R ben. Ez egyrtelm , mert minden R -beli gmb vagy sk elll g hiperskmetszetnek vetleteknt A ttelnk els felttele a 4.15 ttel els felttelt elgti ki, hiszen a paraboloidfelleten a gmbk s 3-dimenzis parabolk elvlasztsai a megfelel hiperskok elvlasztsait jelentik. 4.15 msodik felttele abbl kvetkezik, hogy a g paraboloidnak nincs hrom kollineris pontja. A harmadik pedig a mostani msodik felttelbl 4 3 2 4.20 Kvetkezmny: Legyenek Pa s Pb rendre na  nb elem diszjunkt ponthalmazok R -ban. = Ekkor a Pa s a Pb pontjai kzt elfordul

tvolsgok = kz l a minimlis O(na nb + na + nb )-szer lp fel. 3 2 3 2 3 Bizonyts: Legyen a minimlis tvolsg l > 0. Rajzoljunk Pa minden pontja kr l sugar gmbt. Az na gmb s Pb rendszerre teljeslnek a fenti 4.19 ttel felttelei: Pb minden pontja a gmbkn kvl van s hrom azonos sugar de klnbz centrum gmb metszete nem lehet egy kr. 2 ttekints: A grfok metszsi szmnak felhasznlsval Szkely Lszl elegns bizonytst tallt a Szemerdi-Trotter ttelre Pach Jnos s Micha Sharir pedig nemtrivilis fels korltot adott pontok s kombinatorikus grbk illeszkedseinek szmra. Magasabb dimenziban ez a mdszer nem hasznlhat, mert a tbb dimenzis an altereket reprezentlni kpes (hiper-)grfokra nem ismert mg az Euler-ttelnek megfelel eredmny. A Szemerdi-Trotter ttelbl Rd-ben csak pontok s egyenesek vagy pedig dualitssal 1 ill. 2 kodimenzis an alterek illeszkedseire nyerhet les becsls. Vlemnyem szerint rvnyes fels korltot

ad Rd-ben a Pach-Sharir-ttelbeli I = O(nk= k; e k; = k; + n + e), ahol e a kombinatorikus felletek szmt jelli ( l dimenzis fellet az f : Rl ! Rd fggvny grfja.), azzal a felttellel, hogy k adott pontra legfeljebb s fellet illeszkedhet s kt fellet metszetben legfeljebb s adott pont lehet. Ezt a sejtst kzelti meg a 413 ttel R -ban skokkal s pontokkal, s ennek a dulisnak felel meg a 4.15 ill 419 ttel Ezeknek a tteleknek az ismert (ismertetett) bizonytsa nehezen ltalnosthat ad-hoc elemeket tartalmaz. A 413 ttelben az U hatrn a skbeli Euler-ttelt hasznljuk, a 4.15 ttelben az egyszer politpokra vonatkoz formulkat A (d ; 1)-nl kisebb dimenzis an alterek kezelsekor az is nehzsget jelent, hogy ezek nem adnak elvlasztst Rd-ben. (2 1) (2 2) (2 1) 3 + 49 Ksznetnyilv n t s: Ksznettel tartozom Elekes Gyrgynek a problmakrben s a kapcsold szakirodalomban val eligazods megknnytsrt s a dolgozat elkszltt ksr segt

gyelmrt, Szab Endrnek s Csiks Balzsnak hasznos megjegyzseikrt s tancsaikrt, valamint Fleiner Balzsnak az x g program hasznlathoz nyjtott segtsgrt. Irodalom 1] P.K Agarwal, Pach J:Combinatorial Geometry, 1995 180-181 old John Wiley & Sons., New York 2] M. Ajtai, V Chvtal, M Newborn, Szemerdi E :Crosing-free subgraphs 1982 Annals of Discrete Mathematics, 12., 9-12 3] Beck Jzsef: On the lattice property of the plane and some problems of Dirac, Motzkin and Erds in combinatorial geometry 1983 Combinatorica, 3., 281-297 4] F.RKChung, Szemerdi E, WT Trotter: The number of di&ernet distances determined by a set of points in the Eucledean plane 1992 Discrete and Computational Geometry, 7, 1-11 5] F.RKChung: Point-and-Sphere incidence relation in high dimensions with applications to unit distances and furthest-neighbour pairs 1989 Discrete and Computational Geometry, 2.,195-222 6] K.L Clarkson: New application of random sampling in computational

geometry 1987 Discrete and Computational Geometry, 2., 195-222 7] K.L Clarkson, H Edelsbrunner, LJ Guibas, M Sharir s E Welzl: Combinatorial complexity bounds for arrangements of curves and spheres 1990, Discrete and Computational Geometry, 5., 99-160 8] K.L Clarkson, PW Shor: Applications of random sampling in computational geometry II 1989 Discrete and Computational Geometry, 4, 387-421. 9] G.A Dirac: Collinearity properties of sets of points 1951 Quarterly Journal of Mathematics, 2., 221-227 10] Herbert Edelsbrunner: Algorithms in Combinatorial Geometry 1987 Springer-Verlag, EATCS. 50 11] H. Edelsbrunner, L Guibas, M Sharir: The complexity of many cells in arrangements of planes and related problems 1990 Discrete and Computational Geometry, 5., 197-216 12] E. Edelsbrunner, D Haussler: The complexity of cells in threedimensional arrangements 1986 Discrete Mathematics, 60, 139-147 13] H. Edelsbrunner, M Sharir: A hyperplane incidence problem with applications

to counting distances 1991 Discrete and Computational Geometry, 4,253-263 14] Elekes Gyrgy: On the number of sums and products 1997 megjelens alatt 15] Elekes Gyrgy, Ruzsa Imre: Convexity and sumsets 1997 megjelens eltt 16] J. Ericson: New lower bounds for Hopcroft's problem 1996 Discrete and Computational Geometry, 16., 389-418 17] Erds P., RK Guy: Crossing number problems 1973 American Mathematical Monthly, 80, 50-58 18] Erds Pl: On sets of distances of n points 1946 American Mathematical Monthly, 53., 248-250 19] Erds Pl, Szemerdi Endre: On sums and products of integers 1983 in Erds P., Alpr L, Halsz G: Studies in pure math, To the memory of Paul Turn Akadmiai kiad-Birkh(user Verlag 213-218. 20] Kvri T., TSs Vera, Turn Pl: On a problem of Zarankiewicz 1954 Colloquium Mathematicum, 3. , 50-57 21] F.T Leighton: Complexity issues in VLSI, Foundations of computing series 1983 MIT Press, Cambridge, Mass. 22] T.S Motzkin: The lines

and planes connecting the points of a nite set 1951 Transactions of American Mathematical Society, 70., 451-464 23] Pach Jnos, Micha Sharir: Repeted angles in the plane and related problems 1992 Journal of Combinatorial Theory, Ser. A, 59, 12-22 24] Pach J., M Sharir: On the number of incidences between points and curves 1996, megjelens alatt. 25] George Purdy: Two results about points, lines and planes 1986 Discrete Mathematics, 60., 215-218 51 26] Ruzsa Imre: Arithmetical prograssions and the number of sums 1992 Periodica Mathematica 25., 105-111 27] F.Shahrokhi, O S)kora, Szkely L, I V*to: Crossing numbers: bounds and applications Intuitive Geometry Budapest, 1995 Bolyai Society Mathematical Studies 6. 28] J.Spencer, Szemerdi E, WT Trotter: Unit distances in the Euclidean plane in Graph Theory and Combinatorics, 1984, Academic Press, London, 293-303. 29] Szemerdi E., WTTrotter: Extremal problems in discrete geometry 1983 Combinatorica, 3., 381-392 30]

Szemerdi E., WT Trotter: A combinatorial distinction between the Euclidean and projective planes 1983 European Journal of Combinatorics, 4., 385-394 31] Szkely Lszl: Crossing numbers and hard Erds problems in discrete geometry megjelens alatt Combinatorics, Probability and Computing. 52