A teremőr probléma speciális sokszögekre

Dátum
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

A teremőr probléma egy síkbeli láthatósági probléma, amelyben arra a kérdésre keressük a választ, hogy legalább hány őrre van szükség egy n-oldalú sokszög alaprajzú terem vagy múzeum őrzéséhez. Pontosabban megfogalmazva: legalább hány pontot kell választanunk egy n-oldalú sokszögben ahhoz, hogy a sokszög minden pontja látható legyen ezek valamelyikéből? Ezt a kérdést először Victor Klee vetette fel 1973-ban, amelyre két évvel később Vasek Chvátal adott választ, amikor bebizonyította, hogy bármely n-oldalú sokszög alaprajzú terem őrzéséhez elegendő az oldalszám harmadával megegyező számú őr és tetszőlegesen nagy n esetén található olyan n-oldalú sokszög, amelynél valóban szükség van ennyi őrre. Ez az ún. Chvátal-féle teremőr tétel. A teremőr probléma később matematikusok generációit inspirálta a síkbeli láthatósági problémák tanulmányozására, akik a probléma számos különböző változatát dolgozták ki és oldották meg, amelyek között akadnak máig megválaszolatlanok. A dolgozatban az alap teremőr problémára adott Chvátal-féle megoldás ismertetése mellett a Victor Klee kérdésére adható választ olyan speciális alakú sokszögek esetén vizsgáljuk, mint csillagszerű, spirális vagy monoton sokszögek. Látható, hogy a sokszög alakjára tett megszorítás számos esetben lehetővé teszi, hogy a szükséges őrök számát jelentősen csökkentsük, ami különösen akkor szembetűnő, ha a sokszög oldalszáma helyett egy másik geometriai adat, a konkáv csúcsok számával fejezzük ki az őrök számát. Ezen felül megvizsgáljuk, hogy milyen hatással van az őrök számára adható korlátra, ha az őrök helyzetére megszorításokat teszünk (pl. az őrök csak a csúcsokban állhatbak). Végül meghatározzuk a szükséges őrök minimális számát abban az esetben is, ha az őrök mozoghatnak, külön vizsgálva azokat az eseteket, amikor az őrök útvonalára különféle megszorításokat teszünk. Mindezek mellett számos példát is bemutatunk annak igazolására, hogy a legtöbb állítás esetében szereplő korlátok tovább már nem javíthatók. A dolgozatban található tételek és példák nagy része megtalálható Joseph O'Rourke 1987-es Art Gallery Theorems and Algorithms című könyvében, viszont az abban szereplő eredményeket aktualizáltuk, illetve a példákat jelentősen pontosítva mutatjuk be, bizonyos esetekben segédtételek felhasználásával igazolva, hogy az adott példa valóban elkészíthető.

Leírás
Kulcsszavak
geometria, teremőr probléma
Forrás