Többszörös fedések zárt sokszögekkel
Többszörös fedések zárt sokszögekkel
Kovács István, BSc III. évf.
Témavezető: Tóth Géza, tud. tanácsadó, MTA Rényi Intézet, és docens, BME SZIT
A sík sokszoros fedéseinek vizsgálatát 50 éve Fejes Tóth László és Harold Davenport kezdeményezték. Egy síkbeli halmazokból álló H halmazrendszert k-szoros fedésnek nevezünk, ha a sík minden pontját legalább k halmaz tartalmazza. A legtöbbet vizsgált eset az, amikor H elemei egy adott S halmaz eltoltjai.
Tegyük fel, hogy a S halmaz eltoltjaival k-szorosan lefedtük a síkot, vagyis az eltoltakból álló H halmazrendszer egy k-szoros fedés. Igaz, hogy ha k elég nagy, akkor a fedés felbontható két (vagy több) fedésre? Pontosabban, léteznek-e olyan páronként diszjunkt S1, S2, … Sn részrendszerek, amelyek mindegyike fedés?
Ez az egyszerű kérdés meglepően nehéz és mély problémákhoz vezet, amelyek nagy része máig megoldatlan. A kérdésnek, elméleti jelentősége és érdekessége mellett fontos gyakorlati alkalmazása is van, a szenzor-rendszerek ütemezésénél. Ezért ezzel a kérdéskörrel sokan foglalkoztak az utóbbi időben, különböző módszereket bevetve.
Egy síkbeli S halmazt fedés-felbonthatónak hívunk, ha létezik olyan k = k(S) szám, hogy a sík tetszőleges k-szoros fedése S eltoltjaival felbomlik két fedésre. 1980-ban Pach János vetette fel, hogy határozzuk meg a fedés-felbontható halmazokat. Sejtése szerint minden konvex halmaz fedés-felbontható. 1986-ban bebizonyította, hogy minden nyílt, konvex, középpontosan szimmetrikus sokszög fedés-felbontható. 1987-ben Peter Manival bebizonyították, hogy a nyílt egységkör is fedés-felbontható, bár ezt máig nem publikálták. 20 évvel később Tardos Gábor és Tóth Géza nyílt háromszögekre, Pálvölgyi Dömötör és Tóth Géza pedig minden nyílt konvex sokszögre belátták hogy fedés-felbonthatók. Ugyanakkor Pach, Tardos és Tóth 2007-es eredménye alapján a konkáv négyszögek nem fedés-felbonthatók, Pálvölgyi 2010-ben ezt általánosítva konkáv sokszögek egy tág osztályáról mutatta meg, hogy nem fedés-felbonthatók. Ezeknek az eredményeknek számos további általánosítása, javítása született.
Az összes eddigi pozitív eredmény kizárólag nyílt sokszögekre (illetve körlapra) érvényes, zártakra csak akkor működnek a bizonyítások, ha feltesszük, hogy a fedés lokálisan véges, vagyis a sík minden pontja véges sokszor van lefedve. Meglepő, hogy éppen a végtelenszer fedett pontok okozzák a nehézséget, hiszen úgy is gondolhatjuk, hogy éppen ezeknél van a legtöbb szabadságunk a fedés felbontására.
A dolgozat fő eredménye, hogy bebizonyítjuk, hogy a zárt, konvex, középpontosan szimmetrikus sokszögek is fedés-felbonthatóak.
A fedés-felbonthatóság tulajdonságnak sok egyéb változata van, például a sík fedése helyett vizsgálhatjuk (és felbonthatjuk) tetszőleges halmaz fedéseit is. Ezenkívül szorítkozhatunk csak véges sok illetve megszámlálható sok fedő halmazra, vagy megengedhetünk akármilyen sokat. A dolgozatban megvizsgáljuk a külonböző változatok közti összefüggéseket, és bebizonyítjuk, hogy a nyílt és a zárt, konvex, középpontosan szimmetrikus sokszögek mindegyik változatban fedés-felbonthatóak, sőt a végtelenszeres fedések két, szintén végtelenszeres fedésre is felbonthatóak.
Irodalom:
1. M. Gibson and K. Varadarajan: Decomposing Coverings and the Planar Sensor Cover Problem, arXiv:0905.1093v1, also in: FOCS09 Proceedings.
2. J. Pach: Decomposition of multiple packing and covering, Diskrete Geometrie, 2. Kolloq. Math. Inst. Univ. Salzburg, 169-178, 1980.
3. J. Pach: Covering the plane with convex polygons, Discrete and Computational Geometry 1 (1986), 73-81.
4. D. Pálvölgyi: Indecomposable coverings with concave polygons, Discrete and Computational Geometry 44 (2010), 577-588.
5. D. Pálvölgyi and G. Tóth: Convex polygons are cover-decomposable, Discrete and Computational Geometry 43 (2010), 483-496.
szerző
-
Kovács István
matematika
nappali
