N Kenarlı Çokgen Şeklindeki Bir Galeriyi Korumak İçin Gereken Minimum Nöbetçi Sayısı Kaçtır?
amerikan matematikçi viktor klee tarafından 1973 yılında geliştirilmiş bir problem. soru şöyle:
n kenarlı çokgen (içbükey ya da dışbükey olabilir) şeklinde tasarlanmış bir sanat galerisini korumak için gereken, her biri çokgenin köşelerine yerleştirilmiş ve teorik olarak, bulundukları noktanın görüş açısı içindeki her şeyi görebilecekleri varsayılan minimum nöbetçi sayısı nedir?
19 kenarlı çokgen örneği
i. eğer çokgen dışbükey ise, kenar sayısından bağımsız olarak (sonsuz kenarlı = daire olsa dahi) 1 adet nöbetçi yeterli olacaktır.
12 kenarlı dışbükey çokgen
ii. n kenarlı bir içbükey çokgen için gereken minimum nöbetçi sayısı en fazla tdf (=tam değer fonksiyonu)(n/3) olacaktır*.
(* tam sayı fonksiyonu bir reel sayıya eşit ya da ondan küçük en büyük tamsayıyı vermektedir. yani tdf (5.8)= 5, tdf (-14.5) = -15.)
kanıt
verilen herhangi bir çokgeni görseldeki gibi üçgenlere ayırdığımızda ve elde edilen üçgenlerin köşelerini toplamda üç renk kullanarak ve komşu köşeler aynı renkte olmayacak biçimde, aşağıda görülebileceği gibi renklendirdiğimizde üst sınır olarak n/3 sayıda farklı köşenin (dolayısıyla da n/3 sayıda nöbetçinin) bütün çokgeni taramak için yeterli olacağı anlaşılmaktadır.
3'e tam bölünmeyen sayılar için ise -küsuratlı sayıda kişi sayısı olmayacağı için- tam değer fonksiyonu alınır. (örnekteki 19 kenarlı çokgen için bu sayı tdf (19/3) = 6 olacaktır.)
lemma: tdf (n/3) maksimum yeterli sayı olmakla beraber her zaman gerekli sayı olmayabilir. bir başka deyişle gereken maksimum nöbetçi sayısı bu sayıdan küçük olabilir. söz gelimi örneği verilen (ve sarı köşe sayısının 8, gri köşe sayısının 6 iken mavi köşe sayısının 5 olduğu) 19 kenarlı çokgende, nöbetçileri her birini tamamen dolduracak şekilde sarı, mavi ya da gri köşelere yerleştirmenin bütün galeriyi görebilmek için yeterli olacağı bilgisinden hareketle 8, 6 ya da 5 adet nöbetçi sayısından minimum olanı seçilir. bu da tdf (19/3) = 6 yerine mavi köşe sayısı olan 5'in doğru ve yeterli sayı olacağı anlamına gelmektedir.
örnek 2: şekilde görülebilecek 29 kenarlı, testere biçimindeki çokgen için tdf (29/3)= 9 yerine 3 adet nöbetçi yeterlidir:
iii. iç açıları doksan derece olan (ortogonal olarak adlandırılan) n kenarlı içbükey çokgenler için maksimum yeterli sayı tdf (n/4) olarak verilmektedir:
iv. n kenarlı ve içinde h sayıda kapalı alan barındıran içbükey çokgenler için maksimum yeterli sayı tdf ((n + 5h/3)/4) olarak bulunmuştur:
referanslar:
https://math.mit.edu/…18/nicole_chesnokov_paper.pdf
https://brilliant.org/wiki/guarding-a-museum/
https://en.wikipedia.org/wiki/art_gallery_problem
http://www.math.iit.edu/…lks/longartgallerytalk.pdf
https://reader.elsevier.com/…reation=20210502100927
https://core.ac.uk/reader/11243941
Bir Lunaparkta Birbirini Kaybeden İki Arkadaşın Buluşabilmesi İçin En Verimli Yol Nedir?
