Felezõ félsíkok
Legyen S egy véges ponthalmaz a síkon.
Az egyszerûség kedvéért tegyük fel, hogy
S páros elemszámú és általánso helyzetû
(nincs három eleme egy egyenesen).
S egy elempárja
felezõ,
ha az általuk meghatározott egyenes mindkét oldalára
(|S|-2)/2 darab pont esik S-bõl.
Legfeljebb hány felezõ pár lehet egy n elemû
( 2 | n ) halmazban?
A fenti kérdésre legyen f(n) a válasz.
f(n) nagyságrendjének meghatározása
egy központi kérdése a diszkrét geometriának.
Csupán részerdmények ismertek.
A felsõ becslés terén egy új eredmény
Tamal Dey eredménye, aki
f(n)-re egy n^{4/3} nagyságrendû felsõ becslést
adott. Az elõadás errõl a témakörrõl szólt, benne
Tamal Dey eredményének egy teljes bizonyításával
és még többel is.
Pointerek a témakörhöz:
-
A felezõszakaszok
problémájáról és annak történetérõl
Jeffe Erickson honlapján
olvashatunk.
-
A fenti lapon megtalálható
Tamal Dey
eredeti bizonyítása is.
-
Az elõadáson ismertetett bizonyítás egy kicsit többet ad,
de bonyolultsága nem sokkal több Dey bizonyításáénál.
Ez A. Anrzejak, B. Aronov, S. Har-Peled, R. Seidel és
E. Welzl, Results on k-sets and j-fecets via continuous motions,
Proc. 14th Annual ACM Symposium on Computational Geometry, (1998)
192-199 cikkébõl ered.
A cikk
Emo Welzl
honlapjáról letölthetõ.
-
További rokon problémák
találhatók még
Jeffe Erickson honlapján.