Problema del guarda del museu

El problema del guarda del museu és un problema de visibilitat molt estudiat en l'àmbit de la geometria computacional. Sorgeix d'un problema real en què cal vigilar una galeria d'art amb el mínim nombre de guardes, tal que tota la galeria quedi vigilada. També conegut com a problema de la galeria d'art o, simplement, problema del museu, la versió de geometria computacional la galeria es representa per un polígon i cada guarda per un punt en el polígon. Es diu que un conjunt $S$ de punts guarda un polígon si, per tot punt $p$ del polígon hi ha algun $q$ pertanyent a $S$ tal que la línia entre $p$ i $q$ no surti del polígon.

Dues dimensions

El 1973 Victor Klee va proposar per primera vegada el problema de la galeria d'art i des de llavors han sorgit nombroses variacions del problema inicial. En algunes versions, els guardes tenen un perímetre restringit o fins i tot han d'estar necessàriament als vèrtexs del polígon. En algunes versions només cal vigilar el perímetre o un subconjunt del perímetre.

Resolent la versió en la que els guardes s'han de col·locar ens els vèrtexs i en la que només s'han de vigilar els vèrtexs és equivalent a resoldre el problema del conjunt dominant en el graf de visibilitat del polígon.

El teorema de la galeria d'art de Chvátal

El teorema de la galeria d'art de Chvátal pren el nom de Václav Chvátal,^[1] dona una fita superior pel nombre mínim de guardes necessari. Afirma que sempre són suficients $\left\lfloor {\frac {n}{3}}\right\rfloor$ guardes i que de vegades són necessaris per guardar un polígon simple amb $n$ vèrtexs.

El 1973, en Victor Klee va proposar a Chvátal el problema de trobar quants vèrtexs/guardes calien. Chvátal ho va demostrar poc temps després. Posteriorment Steve Fisk va simplificar la demostració de Chvátal utilitzant un acoloriment amb 3 colors.

Referències

↑ Chvátal, V. «A combinatorial theorem in plane geometry». Journal of Combinatorial Theory, Series B, 18, 1975, p. 39–41. DOI: 10.1016/0095-8956(75)90061-1.

Bibliografia

O'Rourke, Joseph. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. ISBN 0-19-503965-3. Arxivat 2009-02-18 a Wayback Machine.
Shermer, Thomas «Recent Results in Art Galleries». Proceedings of the IEEE, 80, 1992, pàg. 1384–1399. DOI: 10.1109/5.163407.

Read other articles:

Rumah Sakit Umum Daerah Dr. Rasidin

Rumah Sakit Umum Daerah dr. RasidinDinas Kesehatan Kota PadangGeografiLokasiJalan Air Paku, Sungai Sapih, Kuranji, Padang, Sumatera Barat, IndonesiaOrganisasiAsuransi kesehatanBPJS KesehatanPendanaanRumah sakit publikJenisRumah sakit umum daerahPelayananStandar pelayanan (tingkat paripurna)berlaku sampai 26 Mei 2022 [1] Ranjang pasien110 tempat tidurSejarahDibuka30 Agustus 2000; 23 tahun lalu (2000-08-30) Rumah Sakit Umum Daerah dr. Rasidin Padang (disingkat RSUD Rasidin Padang) ...

Ust-Belaya

Selo in Chukotka Autonomous Okrug, RussiaUst-Belaya Усть-БелаяSelo[1]Location of Ust-Belaya Ust-BelayaLocation of Ust-BelayaShow map of RussiaUst-BelayaUst-Belaya (Chukotka Autonomous Okrug)Show map of Chukotka Autonomous OkrugCoordinates: 65°29′N 173°17′E / 65.483°N 173.283°E / 65.483; 173.283CountryRussiaFederal subjectChukotka Autonomous Okrug[1]Administrative districtAnadyrsky DistrictPopulation (2010 Census)[2] ...

Ligue des champions de l'UEFA 2012-2013

Ligue des champions de l'UEFA 2012-2013 Généralités Sport Football Organisateur(s) UEFA Édition 58e Lieu(x) Finale : Wembley StadiumLondres, Angleterre Date Finale : 25 mai 2013 Participants 76 clubs européens Site web officiel Site officiel Palmarès Tenant du titre Chelsea FC (1) Vainqueur Bayern Munich (5) Finaliste Borussia Dortmund Demi-finalistes FC Barcelone Real Madrid Meilleur(s) buteur(s) Cristiano Ronaldo (12) Meilleur(s) passeur(s) Zlatan Ibrahimović (7) Navigatio...

سباق باريس روبيه 1896

سباق باريس روبيه 1896 تفاصيل السباقسلسلة1. سباق باريس روبيهالتاريخ19 أبريل 1896المسافات280 كمالبلد فرنسانقطة البدايةPorte Maillot [الإنجليزية]‏نقطة النهايةعدد المتسابقين في البداية51عدد المتسابقين في النهاية32متوسط السرعة30٫162 كم/سالمنصةالفائز جوسيف فيشرالثاني تشارلز ماير الث�...

Praseodymium(III) sulfate

Praseodymium(III) sulfate Praseodymium sulfate octahydrate Names IUPAC name praseodymium(3+); trisulfate Other names Praseodymium sulphate, dipraseodymium trisulphate, praseodymium(III) sulfate Identifiers CAS Number 10277-44-8 Y13510-41-3 (octahydrate) 3D model (JSmol) Interactive image ChemSpider 145346 Y ECHA InfoCard 100.030.553 EC Number 233-622-8 PubChem CID 16585125022097 (octahydrate) CompTox Dashboard (EPA) DTXSID70890652 InChI InChI=1S/3H2O4S.2Pr/c3*1-5(2,3)4;;/h3*(H...

Coppa Italia Dilettanti (Fase C.N.D.) 1993-1994

Voce principale: Coppa Italia Dilettanti 1993-1994. Questa voce sull'argomento edizioni di competizioni calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Coppa Italia Dilettanti(Fase C.N.D.)1993-1994 Competizione Coppa Italia Dilettanti Sport Calcio Edizione 13ª Organizzatore Lega Nazionale Dilettanti Luogo Italia Partecipanti 166 Formula Gironi triangolari Risultati Vincitore Varese(1º titolo) Secondo Tolentino Cronologia d...

Військово-музичне управління Збройних сил України

Військово-музичне управління Збройних сил України Тип військове формуванняЗасновано 1992Країна Україна Емблема управління Військово-музичне управління Збройних сил України — структурний підрозділ Генерального штабу Збройних сил України призначений для планува...

Палатинська капела

lon_sec = lat_dir = region = lon_dir = lat_sec = lat_min = CoordScale = скасований = lon_min = Палатинська капелаітал. Cappella Palatina Головна апсида та тріумфальна арка Головна апсида та тріумфальна арка 38°06′39″ пн. ш. 13°21′13″ сх. д. / 38.11083° пн. ш. 13.35361° сх. д. / 38.11083; 13.35361Координати:...

Congressional Asian Pacific American Caucus

United States congressional caucus Congressional Asian Pacific American Caucus ChairJudy ChuFounderNorman MinetaFoundedMay 16, 1994; 30 years ago (1994-05-16)HeadquartersWashington, D.C.Seats in the House66 / 435 (plus 1 non-voting) Seats in the Senate8 / 100 Seats in the House Democratic Caucus66 / 213 Seats in House Republican Conference0 / 222 WebsiteOfficial website Politics of United StatesPolitical partiesElections The Congressional Asian Pacific American Caucus (CAPAC...

Fernando Villavicencio

Dalam artikel ini, pertama atau paternal nama keluarganya adalah Villavicencio dan nama keluarga maternal atau keduanya adalah Valencia. Fernando VillavicencioVillavicencio pada Januari 2023 Anggota Majelis Nasionaluntuk Daerah Pemilihan NasionalMasa jabatan14 Mei 2021 – 17 Mei 2023 Informasi pribadiLahirFernando Alcibiades Villavicencio Valencia(1963-10-11)11 Oktober 1963Alausí, EkuadorMeninggal9 Agustus 2023(2023-08-09) (umur 59)Quito, EkuadorSebab kematianPemb...

Culasse (moteur)

Pour les articles homonymes, voir Culasse. La culasse est la pièce assurant la fermeture haute du ou des cylindres et, regroupant certaines fonctions d'un moteur à pistons alternatifs. Sur de nombreux types de moteurs, les soupapes d'admission et d'échappement y sont logées. Sa forme et ses caractéristiques sont toujours étroitement liées à l'évolution des moteurs et, plus particulièrement déterminée par le cycle du moteur (4 temps ou 2 temps) le type de distribution et, par la f...

Họ Tầm ma

Họ Tầm maTầm ma gốc lạ (Urtica dioica)Phân loại khoa họcGiới (regnum)Plantae(không phân hạng)Angiospermae(không phân hạng)EudicotsBộ (ordo)RosalesHọ (familia)UrticaceaeJuss., 1789Chi điển hìnhUrticaL., 1753 Các chi Xem văn bản.Danh pháp đồng nghĩa Cecropiaceae C. C. Berg[1] Họ Tầm ma (danh pháp khoa học: Urticaceae) là một họ thực vật có hoa. Tên gọi của họ này có nguồn gốc từ chi Urtica (tầm ma). Urticaceae b...

Fredonia Manufacturing Company

Fredonia Manufacturing Company Rechtsform Company Gründung 1895 Auflösung 1904 Auflösungsgrund Insolvenz Sitz Youngstown, Ohio, USA Branche Automobile Fredonia Fredonia Manufacturing Company war ein US-amerikanischer Hersteller von Automobilen.[1][2] Inhaltsverzeichnis 1 Unternehmensgeschichte 2 Fahrzeuge 3 Modellübersicht 4 Literatur 5 Weblinks 6 Einzelnachweise Unternehmensgeschichte Das Unternehmen hatte seinen Sitz in Youngstown in Ohio. Es stellte ab 1895 einzelne Au...

Antonio Altomonte

Antonio Altomonte Antonio Altomonte (Palmi, 25 novembre 1934 – Roma, 1º gennaio 1987) è stato uno scrittore e giornalista italiano. Indice 1 Biografia 2 Opere 3 Note 4 Collegamenti esterni Biografia Iscritto alla facoltà di giurisprudenza dell'Università di Messina, Altomonte coltivò interessi letterari seguendo le lezioni di letteratura di Giacomo Debenedetti. Incominciò a scrivere racconti e articoli su alcuni giornali, prima sulla Gazzetta del Sud e poi sul Tempo. Nel 1961 si trasf...

النشاط الفدائي الفلسطيني (1949-1956)

رجال الشرطة الاسرائيلية يتفقدون جثث خمسة فدائيين قتلوا بالقرب من نير غاليم عام 1956 يشير النشاط الفدائي الفلسطيني إلى الصراع المسلح عبر الحدود، الذي بلغ ذروته بين عامي 1949 و1956، وشمل إسرائيل والمسلحين الفلسطينيين، ومقرهم أساسا في قطاع غزة، وهو الإقليم الوحيد لمحمية عموم فلس�...

Hyper Japan

Cet article est une ébauche concernant un élément culturel japonais et l’animation et la bande dessinée asiatiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Hyper JapanPrésentationType Exposition périodique (d)Fondation 2010Site web (en) hyperjapan.co.ukLocalisationLocalisation Royaume-Unimodifier - modifier le code - modifier Wikidata Hyper Japan est une exposition périodique ayant li...

Verse

Pour les articles homonymes, voir Verse (homonymie). Cet article est une ébauche concernant l’agriculture. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Verse dans un champ de blé à la suite de pluies importantes (Épône, Yvelines). Le maïs peut être sujet à la verse du fait de sa hauteur importante. Toutefois, si la verse est légère, les plants peuvent se redresser seuls les jours suivant le coup d...

Ignatas Konovalovas

Ignatas KonovalovasIgnatas Konovalovas lors du départ de la 1re étape des Quatre Jours de Dunkerque 2015 à Dunkerque.InformationsNom court Игнатас КоноваловасNaissance 8 décembre 1985 (38 ans)PanevėžysNationalité lituanienneÉquipe actuelle Groupama-FDJSpécialité RouleurÉquipe non-UCI 2006-7.2007Vélo-Club La Pomme MarseilleÉquipes UCI 8.2007-2007Crédit Agricole (stagiaire)2008Crédit Agricole2009-2010Cervélo TestTeam2011-2012Movistar Team2013-2014MTN-...

Brocken

Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Brocken (Begriffsklärung) aufgeführt. Brocken Der Brocken von Torfhaus aus gesehen Höhe 1141,2 m ü. NHN [1] Lage Sachsen-Anhalt, Deutschland Gebirge Harz (Hochharz) Dominanz 224 km → Fichtelberg (Erzgebirge) Schartenhöhe 856 m ↓ bei Weißenborn-Lüderode[2] Koordinaten 51° 47′ 57″ N, 10° 36′ 56″ O51.799110.61561141.2Koord...

Archdiocese of Uppsala

Church of Sweden archdiocese Archdiocese of UppsalaArchidioecesis UpsaliensisUppsala ärkestiftArms of the archdiocese of UppsalaLocationCountrySwedenDeaneries11 kontrakt[1]Coordinates59°51′29″N 17°38′00″E / 59.85806°N 17.63333°E / 59.85806; 17.63333StatisticsParishes82[1]Congregations136[1]InformationDenominationChurch of SwedenEstablished11th century[2]CathedralUppsala CathedralCurrent leadershipBishopKarin Johannesson[...