Sanat galerisi sorunu

Gelen bilgisayar bilimleri , daha doğrusu içinde algoritmik geometri , sanat galerisi sorunu gerçek bir sorun esinlenerek iyi çalışılmış görünürlük sorundur. Aşağıdaki gibi formüle edilmiştir:

"Bir sanat galerisini korumak için kaç muhafız gerekiyor ve bunlar nereye yerleştirilmeli?" "

Resmi olarak, sanat galerisi basit bir çokgenle ve her koruyucu , çokgenin bir noktasıyla temsil edilir . Çokgendeki herhangi bir nokta için, çizgi parçasının poligon içine girdiği ve tamamen poligonun içinde bulunduğu bir nokta varsa, bir nokta kümesinin bir çokgeni izlediği veya kapsadığı söylenir . Muhafızları güvenlik kamerası olarak da yorumlayabiliriz ve taramada tüm galerinin görünür olmasını isteyebiliriz. $S$ $p$ ${\ displaystyle q \ S’de}$ $p$ $q$

Sanat galerisi teoremi

Václav Chvátal tarafından gösterilen sanat galerisi teoremi, minimum koruyucu sayısı için bir üst sınır verir . Diyor :

" Köşeleri olan basit bir çokgeni korumak için veliler yeterlidir ve bu sınıra ulaşılabilir"

değil

{\ displaystyle \ lfloor n / 3 \ rfloor}

Tarihi

İhtiyaç duyulan kaleci sayısı hakkındaki soru , 1973'te Victor Klee tarafından Chvátal'a soruldu . Chvátal bunu kısa süre sonra kanıtladı. Chvátal'ın ispatı, grafik renklendirmeye dayalı bir argüman kullanılarak Steve Fisk tarafından basitleştirildi . Fisk daha sonra Bowdoin Koleji'nde matematik profesörüydü .

Sanat galerisi problemi ve teoremi, dışbükey kaplama , bir çokgeni üçgenleme veya Voronoi diyagramını hesaplama gibi standart algoritmik geometri temalarından daha az bilinir , ancak çeşitli ders kitaplarında ve algoritmik geometri derslerinde yer alır.

Fisk gösterisi

Steve Fisk'in kanıtı kısa ve zariftir: Divine Reasonings kitabında yer almaktadır . Kanıt çoğunlukla aşağıdaki gibidir. Çokgeni nirengi yaparak başlıyoruz (yeni köşeler eklemeden). Nirengi için devam ediyoruz: En az dört köşeli herhangi bir basit çokgenin en az iki "kulağı" olduğu gerçeğini kullanıyoruz. Kulak, iki kenarı çokgenin sınırına ait olan ve üçüncüsü çokgenin içinde bulunan bir üçgendir. Algoritma, böyle bir kulağı bulmaktan, onu çokgenden çıkarmaktan ibarettir, bu da yeni, daha küçük bir çokgen verir, bu nedenle tekrarlama ile 3-renklendirilebilir ve bu renk, kulağın ek tepe noktasını kalan renkle renklendirerek kolayca genişletilebilir. 3 renk renklendirmede, her üçgen 3 rengi içermelidir. Çokgenin her üçgeni o rengin tepe noktası tarafından korunduğundan, renklerden birinin köşeleri geçerli bir koruyucu grubu oluşturur. Üç renk çokgenin n köşesini böldüğünden, en az köşeye sahip renk, en fazla koruyucuya sahip bir dizi geçerli koruyucuyu tanımlar . ${\ displaystyle \ lfloor n / 3 \ rfloor}$

Varyantlar

Chvátal işaretlemesi, köşelerde kalecilerin kısıtlaması, poligon dışında olmayan herhangi bir noktada kalecilere zayıflatılırsa geçerliliğini korur.

Orijinal sanat galerisi teoreminin başka genellemeleri veya uzmanlıkları da vardır. Örneğin, dik çokgenler için, yani kenarları dik açılarla birleşen çokgenler için gereken tek şey koruyuculardır. Bu sonucun en az üç farklı kanıtı vardır, hiçbiri basit değildir, biri Kahn, Maria Klawe ve Daniel Kleitman tarafından yapılmıştır ; bir başka Anna Lubiw tarafından ; ve yine Jörg-Rüdiger Sack ve Godfried Toussaint (en) tarafından . ${\ displaystyle \ lfloor n / 4 \ rfloor}$

Benzer bir sorun, bir çokgenin dışını örtmek için gerekli minimum koruma sayısının belirlenmesidir (bu "kale sorunu" dır): yeterlidir ve bazen de gereklidir. Başka bir deyişle, sonsuz olan dış cepheyi örtmek, bitmiş iç mekanı örtmekten daha zahmetlidir. $\ lceil n / 2 \ rceil$

Algoritmik karmaşıklık

Hesaplama problemi

Çokgenin köşelerine yerleştirilen ve Chvátal işaretlemesini, dolayısıyla çoğu koruyucuyu doğrulayan koruyucu setlerini bulmak için etkili algoritmalar mevcuttur . ${\ displaystyle \ lfloor n / 3 \ rfloor}$

David Avis ve Godfried Toussaint, böyle bir yerleşimin böl ve yönet yöntemi kullanılarak en kötü durum olarak hesaplanabileceğini kanıtladı . Kooshesh ve Moret 1992 , Fisk'in kanıt algoritmasını ve Bernard Chazelle'in doğrusal üçgenleme algoritmasını kullanarak doğrusal bir zaman algoritması verdi . $O (n \ log n)$

Couto, de Rezende ve de Souza 2011 tarafından en üst sıradaki kaleciler için bir hesaplama algoritması önerildi . Yazarlar, birkaç bin köşeli çokgenler için bile en uygun çözümlerin nispeten kısa bir sürede bulunabileceğini gösteren çeşitli poligon sınıflarıyla çok sayıda test gerçekleştirdiler.

Karar sorunu

Bir karar problemi olarak kabul edilen sanat galerisi problemi, bir çokgen ve bir tamsayı k verildiğinde , bu çokgenin en fazla k koruyucu ile tutulup tutulamayacağını belirleme problemidir . Bu sorun -Komple burada, bir karmaşıklık sınıfı varoluşsal fragmanına karşılık gelen kapalı gerçek cisimlerin teorisi . Genel varyasyonlar (koruyucuların konumlarını çokgenin köşeleri veya kenarlarıyla sınırlamak gibi) NP-zordur . ${\ displaystyle \ var \ mathbb {R}}$ ${\ displaystyle \ var \ mathbb {R}}$

Yaklaşıklık

Minimum koruyucu sayısı için bir yaklaştırma algoritmasıyla ilgili olarak, Eidenbenz, Stamm ve Widmayer 2001 , sorunun APX açısından zor olduğunu göstermiştir ; Bu, sabit bir sabitten daha iyi bir yaklaşım oranının , polinom zamanında bir yaklaşım algoritması ile elde edilemeyeceği anlamına gelir . Bununla birlikte, sabit bir yaklaşım oranına sahip hiçbir algoritma bilinmemektedir. Bunun aksine, minimum vasi sayısının logaritmik bir tahmini , problemi belirlenen kapsam problemine indirgeyerek elde edilebilir . Pavel Valtr tarafından, bir sanat galerisi probleminden türetilen küme sisteminin sınırlı bir Vapnik-Tchervonenkis boyutuna sahip olduğu gösterilmiştir; bu , yaklaşık oranı optimalin logaritması olan ε-ağlarına (en) dayalı küme kapsama algoritmalarının uygulanmasını mümkün kılar. çokgenin köşe sayısı yerine koruyucu sayısı. Pozisyonları kısıtlanmayan kaleciler için, potansiyel olarak sonsuz sayıda pozisyon sorunu daha da zorlaştırır. Koruyucuları ince bir ızgara üzerinde pozisyon almaya zorlarsak, ek kısıtlayıcı olmayan varsayımlar altında daha karmaşık bir logaritmik yaklaşım algoritması elde edilebilir.

Üstün boyutlar

Müze daha yüksek boyutta bir çokyüzlü ile temsil ediliyorsa , o zaman müzenin tamamını kapsayacak şekilde her köşeye bir muhafız yerleştirmek yeterli olmayabilir. Polihedronun yüzeyleri o zaman gözetim altında olsa bile, polihedronun içindeki noktaların görünmemesi mümkündür.

Notlar

O'Rourke 1987 , s. 1.
Chvátal 1975 .
Fisk 1978 .
Leghorn, " Matematik profesörü 63 yaşında lösemiden öldü " [ archive du14 Ocak 2017] , Bowdoin Şark,2010.
Berg ve ark. 2008 .
Castelli Aleardi ve Oudot 2012 .
Boissonnat 2017 .
Goodman ve O'Rourke 2004 .
Edelsbrunner 1987 .
Pach ve Agarwal 1995 .
Mehlhorn ve Naeher 1999 .
Fisk 1978 .
Divine Reasons , bölüm 35: "Müze nasıl izlenir?".
Shermer 1992 .
O'Rourke 1987 , s. 37-80, Kahn, Klawe ve Kleitman 1983 , Lubiw 1985 ve Sack and Toussaint 1988 .
O'Rourke 1987 , s. 146-154.
Avis ve Toussaint 1981 .
. Bu testler için veriler ve çözümler Couto, de Rezende ve de Souza 2011'de mevcuttur .
Abrahamsen, Adamaszek ve Miltzow 2017 .
O'Rourke 1987 , s. 239–242; Aggarwal 1984 ; Lee ve Lin 1986 .
Kumar Ghosh 2010 .
Valtr 1998 .
Brönnimann ve Goodrich 1995 .
Deshpande ve diğerleri. 2007
Bonnet ve Miltzow 2017 .
O'Rourke 1987 , s. 255.

Referanslar

Kitabın

Joseph O'Rourke, Sanat Galerisi Teoremleri ve Algoritmaları , Oxford University Press ,1987( ISBN 0-19-503965-3 , çevrimiçi okuyun ).
Mark de Berg, Otfried Cheong, Marc van Kreveld ve Mark Overmars , Hesaplamalı geometri: algoritmalar ve uygulamalar , Springer Verlag ,2008, 3 e ed. , 386 s. ( ISBN 978-3-540-65620-3 ve 3-540-65620-0 , çevrimiçi sunum , çevrimiçi okuyun ) , böl. 3 ("Poligon Üçgenlemesi"), s. 45-61.
Luca Castelli Aleardi ve Steve Oudot, Hesaplamalı geometriye giriş ve uygulamaları , École polytechnique de Paris, coll. "Kurs INF562",2012, 123 p. ( çevrimiçi okuyun ).
Jean-Daniel Boissonnat, Algoritmik geometri: geometrik verilerden veri geometrisine: Kursun açılış dersi , Paris, Librairie Arthème Fayard ve Collège de France,2017, 73 p. ( ISBN 978-2-213-70765-5 ve 978-2-213-70512-5 , çevrimiçi okuyun ).
Jacob E. Goodman ve Joseph O'Rourke (editörler), The Handbook of Discrete and Computational Geometry , CRC Press,2004, 2 nci baskı. ( ISBN 1-58488-301-4 ).
(en) Herbert Edelsbrunner, Kombinatoryal Geometride Algoritmalar , Berlin / Heidelberg / Paris vb., Springer-Verlag , coll. "Teorik Bilgisayar Bilimi Üzerine EATCS Monografları" ( n o 10),1987, 423 s. ( ISBN 3-540-13722-X , çevrimiçi okuyun ).
(tr) János Pach ve Pankaj K. Agarwal, Combinatorial Geometry , New York / Chichester / Brisbane vb., John Wiley & Sons ,1995, 354 s. ( ISBN 0-471-58890-3 ).
(tr) János Pach ve Micha Sharir, Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures , Providence, RI, American Mathematical Society, coll. "Matematiksel Araştırmalar ve Monograflar" ( n o 152)2009, 235 s. ( ISBN 978-0-8218-4691-9 , çevrimiçi okuyun ).
(en) Kurt Mehlhorn ve Stefan Naeher, LEDA, A Platform for Combinatorial and Geometric Computing , Cambridge, Cambridge University Press ,1999, 1018 s. ( ISBN 0-521-56329-1 , çevrimiçi okuyun ).

Nesne

Mikkel Abrahamsen Anna Adamaszek ve Tillmann Miltzow, “ Sanat Galerisi Sorun -tamamlamak ${\ displaystyle \ var \ mathbb {R}}$ ”, ön baskı (arXiv) ,2017( arXiv 1704.06969 ).
Alok Aggarwal, Sanat galerisi teoremi: Varyasyonları, uygulamaları ve algoritmik yönleri (Doktora tezi), Johns Hopkins Üniversitesi,1984.
David Avis ve Godfried T. Toussaint, " Bir çokgeni yıldız şeklindeki çokgenlere ayırmak için etkili bir algoritma ", Pattern Recognition , cilt. 13, n o 6,bin dokuz yüz Seksen bir, s. 395–398 ( DOI 10.1016 / 0031-3203 (81) 90002-9 , çevrimiçi okuyun ).
Édouard Bonnet ve Tillmann Miltzow, " Sanat Galerisi Problemine Yaklaşım Algoritması ", Hesaplamalı Geometri Sempozyumu ,2017, s. 20: 1-20: 15, Makale n o 20 ( arXiv 1607.05527 , çevrimiçi okuyun ).
Hervé Brönnimann ve Michael T. Goodrich, “ Sonlu VC boyutunda neredeyse optimal küme kapakları ”, Ayrık ve Hesaplamalı Geometri , cilt. 14, n o 1,1995, s. 463–479 ( DOI 10.1007 / BF02570718 ).
Václav Chvátal, " Düzlem geometride bir kombinatoryal teorem ", Kombinatoryal Teori Dergisi, Seri B , cilt. 18,1975, s. 39-41 ( DOI 10.1016 / 0095-8956 (75) 90061-1 ).
Marcelo C. Couto , Pedro J. de Rezende ve Cid C. de Souza , " Sanat galerilerinde köşe korumalarını en aza indirmek için kesin bir algoritma ", Uluslararası İşlemler Operasyonel Araştırmalar , cilt. 18, n o 4,2011, s. 425–448 ( DOI 10.1111 / j.1475-3995.2011.00804.x ).
Marcelo C. Couto , Pedro J. de Rezende ve Cid C. de Souza , Köşe korumaları ile sanat galerisi sorunu için kıyaslama örnekleri ,2011( çevrimiçi okuyun ).
Ajay Deshpande, Taejung Kim, Erik Demaine ve Sanjay E. Sarma, "A Pseudopolynomial Time O (logn) -Approximation Algorithm for Art Gallery Problems" , Proc. Atölye Algoritmaları ve Veri Yapıları , Springer-Verlag, coll. "Bilgisayar Bilimlerinde Ders Notları" ( n o 4619),2007( ISBN 978-3-540-73948-7 , DOI 10.1007 / 978-3-540-73951-7_15 ) , s. 163–174.
.
Steve Fisk, " Chvátal'ın bekçi teoreminin kısa bir kanıtı ", Journal of Combinatorial Theory, Series B , cilt. 24, n o 3,1978, s. 374 ( DOI 10.1016 / 0095-8956 (78) 90059-X ).
Subir Kumar Ghosh, " Çokgenlerdeki sanat galerisi problemleri için yaklaşım algoritmaları ", Ayrık Uygulamalı Matematik , cilt. 158, n o 6,2010, s. 718-722.
J. Kahn, Maria M. Klawe ve Daniel J. Kleitman, " Geleneksel galeriler daha az bekçi gerektirir ", SIAM J. Alg. Disk. Meth. , cilt. 4, n o 21983, s. 194–206 ( DOI 10.1137 / 0604020 ).
Ali A. Kooshesh ve Bernard ME Moret, "Üçgenleştirilmiş basit bir çokgenin köşelerini üç kez renklendirmek ", Desen Tanıma , cilt. 25, n, o , 4,1992, s. 443 ( DOI 10.1016 / 0031-3203 (92) 90093-X ).
Der-Tsai Lee ve AK Lin, " Sanat galerisi problemlerinin hesaplamalı karmaşıklığı ", IEEE İşlemleri Bilgi Teorisi , cilt. 32, n o 21986, s. 276–282 ( DOI 10.1109 / TIT.1986.1057165 ).
Anna Lubiw, "Poligonal bölgelerin dışbükey dörtgenlere ayrıştırılması" , Proc. Hesaplamalı Geometri 1. ACM Sempozyumu ,1985( ISBN 0-89791-163-6 , DOI 10.1145 / 323233.323247 ) , s. 97–106.

Jörg-Rüdiger Sack ve Godfried Toussaint, Godfried Toussaint (editör), Computational Morphology , North-Holland'da "doğrusal çokgenlerde koruma yerleştirme" ,1988, s. 153–176.
Thomas Shermer, " Sanat Galerilerinde Son Sonuçlar ", IEEE Bildirileri , cilt. 80, n o 9,1992, s. 1384–1399 ( DOI 10.1109 / 5.163407 , çevrimiçi okuma ).
Pavel Valtr, " Hiçbir noktanın küçük bir alanı görmediği galerileri koruma ", Israel J. Math. , cilt. 104, n o 1,1998, s. 1–16 ( DOI 10.1007 / BF02897056 ).

İlgili Makaleler