Büyük bir sanat galerisinde güvenlik şefi olduğunuzu hayal edin. Galeri duvarlarını kaplayan çok değerli tablolar var. Sizin de göreviniz bu tabloları korumak. Galeri, farklı şekil ve büyüklükteki odalardan oluşuyor. Ancak her bir resmin başına bir görevli dikecek kadar da paranız yok. Bu durumda en az sayıda güvenlik görevlisi kullanarak galerideki tüm resimlerin güvenliğini nasıl sağlayabilirsiniz? Okuduğunuz bu probleme Art gallery problem yani sanat galerisi problemi / müze problemi denir. Bu soru hesaplamalı geometrideki önemli sorulardan birisidir.
Problem 1973’te Victor Klee tarafından ortaya atılmış ve 1975’te Vaclav Chvátal tarafından ispatı yapılmıştır. Ancak bu ispat oldukça karışık olduğu için problemin ikinci ve daha kısa bir ispatı 1978’de Steve Fisk tarafından gerçekleştirilmiştir. Geometrik terimlerle, problem şu şekildedir: n-köşeli bir basit çokgen verildiğinde, çokgenin içinin her noktasını görmek için minimum koruma sayısı nedir?
Hesaplamalı geometri, geometrik olarak ifade edilebilen algoritmaların incelenmesine ayrılmış bilgisayar bilimlerinin bir dalıdır. Hesaplamalı geometride problemler matematiksel görselleştirme ve modelleme yoluyla bilgisayar bilimlerine dahil edilmiştir. Bu tarz geometri problemleri gerçekçi bir kullanıcı deneyimi yaratmak için genellikle sanal bir dünyaya dayalı hesaplamalar yapmanın gerekli olduğu video oyunu programlamasında da doğal olarak karşımıza çıkar. Şimdi problemin çözümüne geçebiliriz.
Galerinin Güvenliğini Sağlamak İçin Gerekli En Az Sayıda Kişiyi Nasıl Belirleyebiliriz?
Problemde tüm duvarları izlemek için gereken minimum koruma sayısını bilmemiz gerekiyor. Duvarların düz olduğunu ve iki duvarın birleştiği bir köşede bulunan bir muhafızın her iki duvardaki her şeyi görebileceğini varsayalım. Ayrıca, bir muhafızın görüşünün hiçbir zaman engellenmediğini ve 360 derece etrafında dönebileceğini kabul edeceğiz. Son olarak korumalarımız hareket etmeyecek. Çokgenin köşelerinde bulundukları yerden etrafı gözlemleyecekler.
Üçgen biçiminde bir galeri, tek bir güvenlik görevlisi tarafından her zaman rahatça kontrol edilecektir. Aslında, galerimiz sadece üçgen değil herhangi bir dışbükey çokgen ( dikdörtgen, beşgen…) olduğu zaman bir görevli yeterlidir. Ancak eğer galerimizin şekli girintilere sahip ise o zaman işler karışmaya başlıyor. Örneğin aşağıdaki biçimde olan 12 duvarlı bir galeriyi ele alalım. Bu galeri için 4 koruma görevlisi yeterli olacaktır.
İhtiyaç duyulan koruma görevlisinin sayısının çokgenin köşelerinin sayısına bağlı olacağı sezgisel olarak anlaşılmaktadır. Bu yüzden girintili çıkıntılı şekle sahip olan bir galeriyi güvende tutmak için onu çokgenlere ayırmalıyız. Böylece her çokgenin içine bir güvenlik görevlisi yerleştirmek mümkün olacaktır. Fisk’in zekice argümanı, n köşeli basit bir çokgen şeklindeki bir galeriyi korumak için asla n/3’ün tam kısmından fazla korumaya ihtiyacınız olmadığını bize gösterir. On iki kenarlı yukarıdaki galerimiz için bu değer maksimum 12/3 = 4 iken sekiz kenarlı galeri için ikidir.
Sanat Galerisi Probleminin Olası Çözümleri
Genel olarak sorunu çözmek için galeriyi üst üste binmeyen üçgenlere nasıl bölebileceğimize bakacağız. Eğer bir çokgenin S kadar kenarı var ise bu çokgen S-2 kadar üçgene ayrılacaktır. Bu durumda da ayırdığımız üçgen sayısı kadar güvenlik görevlisi yeterli olacaktır. Ancak daha az sayıda gerekli koruma sayısının bulunması da mümkündür. Çünkü karşı köşegenleri birleştirerek bir kareyi her zaman iki üçgene bölebiliriz. Ancak tüm duvarları izlemek için iki korumaya ihtiyacımız yoktur. Sonuçta bir kişi aslında yeterlidir.
Bu nedenle gerekli güvenliği sağlamak için daha az görevli gerektiren dikdörtgenlere ayırma daha kullanışlı olacaktır. Bu durumda da galeriyi korumak için gerekli koruma sayısı ¼ × Köşe Sayısının tam sayı kısmı biçiminde olacaktır. Aşağıdaki on dört köşeli galeri için bu sayı üçtür.
Bir başka geleneksel dik açılı galeri türü, odalara bölünen biçimlidir. Aşağıda on odalı örnek bir galeri örebilirsiniz.
Bu durumda da galeriyi dikdörtgenlere bölmek daha mantıklıdır. İki farklı odayı birbirine bağlayan açıklığa bir koruma yerleştirirseniz, iki oda da aynı anda güvende olur. Öyleyse bu durumda galeride gerekli olan güvenlik görevlisi sayısı, ½ × Oda Sayısı’na eşit veya ondan büyük bir sonraki tam sayı biçiminde olur. Yukarıdaki görseldeki on odalı galeri için bu beştir.
Sonuç Olarak;
Sanat galerisi problemi ile ilgili harika olan şey matematikçilere keşfedilecek bir dizi yeni yol sunmasıdır. Bazılarında muhafızların hareket ettiği, bazılarında sınırlı görüş alanlarına sahip oldukları veya köşeleri görmelerine yardımcı olacak aynaların olduğu her türlü senaryo matematikçiler tarafından incelenmiştir. ( Kaynaklarda bu gibi detaylara erişebilirsiniz.). Gerçek dünyada bir sanat galerisine güvenlik görevlisi alınırken bu hesaplamalara göre hareket edilmese de aynı yaklaşım güvenlik kameralarının konumlandırılmasında kullanılmaktadır.
Kaynaklar ve İleri Okumalar:
- The art gallery problem; yayınlanma tarihi: 14 Temmuz 2014; Bağlantı: https://plus.maths.org/content/art-gallery-problem
- Art gallery problem; Bağlantı: https://en.wikipedia.org
- John D. Barrow; 100 Essential Things You Didn’t Know You Didn’t Know about Math and the Arts; ISBN: 0393352226
Matematiksel
