http://fr.dbpedia.org/resource/Problème_de_la_galerie_d'art (original) (raw)
En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit : « Quel est le nombre de gardiens nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? »
| Property | Value |
|---|---|
| dbo:abstract | En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit : « Quel est le nombre de gardiens nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? » Formellement, la galerie d'art est représenté par un polygone simple et chaque gardien par un point du polygone. Un ensemble de points est dit surveiller ou couvrir un polygone si, pour tout point du polygone, il existe un point tel que le segment de droite entre et est entièrement contenu dans le polygone. On peut aussi interpréter les gardiens comme des caméras de surveillance et demander que l'ensemble de la galerie soit visible en balayage. (fr) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Triangulation_3-coloring.svg?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=mxugg47mzK4C&printsec=frontcover https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf http://www.enseignement.polytechnique.fr/informatique/INF562/Notes/Poly_INF562.pdf http://drops.dagstuhl.de/opus/volltexte/2017/7215/ http://www.cs.uu.nl/geobook/ http://cgm.cs.mcgill.ca/~godfried/publications/star.pdf http://www.cs.ubc.ca/nest/theory/thread/papers/shermer2002.pdf http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html http://liseuse-hachette.fr/file/43055 http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/ http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf https://books.google.com/books%3Fid=vKT0BwAAQBAJ&printsec=frontcover https://books.google.com/books%3Fid=Q2aXZl3fgvMC&printsec=frontcover |
| dbo:wikiPageID | 11387313 (xsd:integer) |
| dbo:wikiPageLength | 19866 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 178673216 (xsd:integer) |
| dbo:wikiPageWikiLink | dbpedia-fr:APX_(complexité) dbpedia-fr:Algorithme_d'approximation dbpedia-fr:Anna_Lubiw dbpedia-fr:Bernard_Chazelle dbpedia-fr:Bowdoin_College dbpedia-fr:Cambridge_University_Press category-fr:Graphe_géométrique category-fr:Géométrie_algorithmique category-fr:Polygone category-fr:Problème_algorithmique dbpedia-fr:Classe_de_complexité dbpedia-fr:Coloration_de_graphe dbpedia-fr:Complexité_en_temps dbpedia-fr:Conférences_WADS_et_SWAT dbpedia-fr:Corps_réel_clos dbpedia-fr:Daniel_Kleitman dbpedia-fr:Diagramme_de_Voronoï dbpedia-fr:Dimension_de_Vapnik-Chervonenkis dbpedia-fr:Diviser_pour_régner_(informatique) dbpedia-fr:Enveloppe_convexe dbpedia-fr:Galerie_d'art dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Géométrie_algorithmique dbpedia-fr:Informatique dbpedia-fr:John_Wiley_&_Sons dbpedia-fr:Jörg-Rüdiger_Sack dbpedia-fr:Kurt_Mehlhorn dbpedia-fr:Logarithme dbpedia-fr:NP-difficile dbpedia-fr:Nombre_de_Catalan dbpedia-fr:Oxford_University_Press dbpedia-fr:Point_(géométrie) dbpedia-fr:Polygone_simple dbpedia-fr:Polyèdre dbpedia-fr:Problème_de_couverture_par_ensembles dbpedia-fr:Problème_de_décision dbpedia-fr:Raisonnement_par_récurrence dbpedia-fr:Raisonnements_divins dbpedia-fr:Segment_(mathématiques) dbpedia-fr:Springer_Science+Business_Media dbpedia-fr:Théorie_existentielle_sur_les_réels dbpedia-fr:Triangulation_d'un_ensemble_de_points dbpedia-fr:Triangulation_d'un_polygone dbpedia-fr:Triangulation_de_Delaunay dbpedia-fr:Victor_Klee dbpedia-fr:Václav_Chvátal dbpedia-fr:Fichier:Triangulation_3-coloring.svg dbpedia-fr:Majorant_ou_minorant dbpedia-fr:Maria_Klawe dbpedia-fr:Mark_Overmars dbpedia-fr:Fichier:Art_gallery_problem.svg dbpedia-fr:Fichier:Festung-freie-wächter.svg dbpedia-fr:Fichier:Polyhedron_with_no_vertex_visible_from_center.png |
| prop-fr:année | 1975 (xsd:integer) 1978 (xsd:integer) 1981 (xsd:integer) 1983 (xsd:integer) 1984 (xsd:integer) 1985 (xsd:integer) 1986 (xsd:integer) 1987 (xsd:integer) 1988 (xsd:integer) 1992 (xsd:integer) 1995 (xsd:integer) 1998 (xsd:integer) 1999 (xsd:integer) 2001 (xsd:integer) 2004 (xsd:integer) 2007 (xsd:integer) 2008 (xsd:integer) 2009 (xsd:integer) 2010 (xsd:integer) 2011 (xsd:integer) 2012 (xsd:integer) 2017 (xsd:integer) |
| prop-fr:archivedate | 2003-06-24 (xsd:date) |
| prop-fr:archiveurl | https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf |
| prop-fr:articleNuméro | 20 (xsd:integer) |
| prop-fr:arxiv | 1607.055270 (xsd:double) 1704.069690 (xsd:double) |
| prop-fr:auteur | dbpedia-fr:Kurt_Mehlhorn dbpedia-fr:Mark_Overmars Herbert Edelsbrunner (fr) Marc van Kreveld (fr) Mark de Berg (fr) Erik Demaine (fr) Václav Chvátal (fr) János Pach (fr) Jacob E. Goodman (fr) Michael T. Goodrich (fr) Pavel Valtr (fr) Hervé Brönnimann (fr) Jean-Daniel Boissonnat (fr) Micha Sharir (fr) Pankaj K. Agarwal (fr) Subir Kumar Ghosh (fr) Daniel J. Kleitman (fr) Joseph O'Rourke (fr) A. K. Lin (fr) Ajay Deshpande (fr) Ali A. Kooshesh (fr) Alok Aggarwal (fr) Anna Adamaszek (fr) Anna Lubiw (fr) Bernard M. E. Moret (fr) Christoph Stamm (fr) David Avis (fr) Der-Tsai Lee (fr) Godfried T. Toussaint (fr) Godfried Toussaint (fr) J. Kahn (fr) Jörg-Rüdiger Sack (fr) Luca Castelli Aleardi (fr) Maria M. Klawe (fr) Mikkel Abrahamsen (fr) Otfried Cheong (fr) Peter Widmayer (fr) Sanjay E. Sarma (fr) Stefan Naeher (fr) Stephan Eidenbenz (fr) Steve Fisk (fr) Steve Oudot (fr) Taejung Kim (fr) Thomas Shermer (fr) Tillmann Miltzow (fr) Édouard Bonnet (fr) |
| prop-fr:auteurOuvrage | Godfried Toussaint (fr) |
| prop-fr:collection | EATCS Monographs on Theoretical Computer Science (fr) Mathematical Surveys and Monographs (fr) Cours INF562 (fr) |
| prop-fr:consultéLe | 2018-01-12 (xsd:date) |
| prop-fr:doi | 10.100700 (xsd:double) 10.101600 (xsd:double) 10.110900 (xsd:double) 10.111100 (xsd:double) 10.113700 (xsd:double) 10.114500 (xsd:double) |
| prop-fr:fr | Couverture d'un polygone (fr) Godfried Toussaint (fr) Polygone anthropomorphe (fr) ε-réseau (fr) |
| prop-fr:id | CRSa (fr) CRSb (fr) |
| prop-fr:isbn | 0 (xsd:integer) 1 (xsd:integer) 3 (xsd:integer) 978 (xsd:integer) |
| prop-fr:journal | Proceedings of the IEEE (fr) Algorithmica (fr) Discrete Applied Mathematics (fr) IEEE Transactions on Information Theory (fr) Israel J. Math. (fr) Journal of Combinatorial Theory, Series B (fr) Discrete and Computational Geometry (fr) preprint (fr) Pattern Recognition (fr) International Transactions in Operational Research (fr) SIAM J. Alg. Disc. Meth. (fr) Symposium on Computational Geometry (fr) |
| prop-fr:langue | en (fr) fr (fr) |
| prop-fr:lienAuteur | Maria Klawe (fr) |
| prop-fr:lieu | Cambridge (fr) Paris (fr) Providence, R.I. (fr) New York/Chichester/Brisbane etc. (fr) Berlin/Heidelberg/Paris etc. (fr) |
| prop-fr:lireEnLigne | https://books.google.com/books%3Fid=mxugg47mzK4C&printsec=frontcover http://www.enseignement.polytechnique.fr/informatique/INF562/Notes/Poly_INF562.pdf http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html http://liseuse-hachette.fr/file/43055 http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/ https://books.google.com/books%3Fid=vKT0BwAAQBAJ&printsec=frontcover https://books.google.com/books%3Fid=Q2aXZl3fgvMC&printsec=frontcover |
| prop-fr:natureOuvrage | thèse Ph. D. (fr) |
| prop-fr:nom | de Souza (fr) Couto (fr) de Rezende (fr) |
| prop-fr:numéro | 1 (xsd:integer) 2 (xsd:integer) 3 (xsd:integer) 4 (xsd:integer) 6 (xsd:integer) 9 (xsd:integer) |
| prop-fr:numéroArticle | 20 (xsd:integer) |
| prop-fr:numéroChapitre | 3 (xsd:integer) |
| prop-fr:numéroD'édition | 2 (xsd:integer) 3 (xsd:integer) |
| prop-fr:numéroDansCollection | 10 (xsd:integer) 152 (xsd:integer) 4619 (xsd:integer) |
| prop-fr:page | 374 (xsd:integer) 443 (xsd:integer) |
| prop-fr:pages | 1 (xsd:integer) 20 (xsd:integer) 39 (xsd:integer) 79 (xsd:integer) 194 (xsd:integer) 276 (xsd:integer) 395 (xsd:integer) 425 (xsd:integer) 463 (xsd:integer) 718 (xsd:integer) 1384 (xsd:integer) |
| prop-fr:pagesTotales | 73 (xsd:integer) 123 (xsd:integer) 235 (xsd:integer) 354 (xsd:integer) 386 (xsd:integer) 423 (xsd:integer) 1018 (xsd:integer) |
| prop-fr:passage | 45 (xsd:integer) 97 (xsd:integer) 153 (xsd:integer) 163 (xsd:integer) |
| prop-fr:prénom | Cid C. (fr) Marcelo C. (fr) Pedro J. (fr) |
| prop-fr:présentationEnLigne | http://www.cs.uu.nl/geobook/ |
| prop-fr:responsabilité | éditeurs (fr) |
| prop-fr:series | Lecture Notes in Computer Science (fr) |
| prop-fr:sousTitre | Leçon inaugurale du cours (fr) The Alcala Lectures (fr) algorithms and applications (fr) |
| prop-fr:texte | ε-réseaux (fr) |
| prop-fr:titre | A short proof of Chvátal's watchman theorem (fr) Combinatorial Geometry (fr) Three-coloring the vertices of a triangulated simple polygon (fr) LEDA, A Platform for Combinatorial and Geometric Computing (fr) Géométrie algorithmique : des données géométriques à la géométrie des données (fr) Benchmark instances for the art gallery problem with vertex guards (fr) A Pseudopolynomial Time O-Approximation Algorithm for Art Gallery Problems (fr) A combinatorial theorem in plane geometry (fr) Algorithms in Combinatorial Geometry (fr) Almost optimal set covers in finite VC-dimension (fr) Art Gallery Theorems and Algorithms (fr) Computational complexity of art gallery problems (fr) Computational geometry (fr) The art gallery theorem : Its variations, applications, and algorithmic aspects (fr) Guard placement in rectilinear polygons (fr) Approximation algorithms for art gallery problems in polygons (fr) Recent Results in Art Galleries (fr) The Art Gallery Problem is -complete (fr) Traditional galleries require fewer watchmen (fr) An Approximation Algorithm for the Art Gallery Problem (fr) Inapproximability results for guarding polygons and terrains (fr) Decomposing polygonal regions into convex quadrilaterals (fr) Combinatorial Geometry and its Algorithmic Applications (fr) Guarding galleries where no point sees a small area (fr) An exact algorithm for minimizing vertex guards on art galleries (fr) Introduction à la géométrie algorithmique et ses applications (fr) An efficient algorithm for decomposing a polygon into star-shaped polygons (fr) The Handbook of Discrete and Computational Geometry (fr) |
| prop-fr:titreChapitre | Polygon Triangulation (fr) |
| prop-fr:titreOuvrage | dbpedia-fr:Conférences_WADS_et_SWAT Computational Morphology (fr) Proc. 1st ACM Symposium on Computational Geometry (fr) |
| prop-fr:trad | Ε-net (fr) Anthropomorphic polygon (fr) Polygon covering (fr) |
| prop-fr:url | http://drops.dagstuhl.de/opus/volltexte/2017/7215/ http://cgm.cs.mcgill.ca/~godfried/publications/star.pdf http://www.cs.ubc.ca/nest/theory/thread/papers/shermer2002.pdf http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf |
| prop-fr:volume | 4 (xsd:integer) 13 (xsd:integer) 14 (xsd:integer) 18 (xsd:integer) 24 (xsd:integer) 25 (xsd:integer) 31 (xsd:integer) 32 (xsd:integer) 80 (xsd:integer) 104 (xsd:integer) 158 (xsd:integer) |
| prop-fr:wikiPageUsesTemplate | dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Chapitre dbpedia-fr:Modèle:Harvsp dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Note dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Sfn dbpedia-fr:Modèle:Google_Livres |
| prop-fr:éditeur | dbpedia-fr:Cambridge_University_Press dbpedia-fr:John_Wiley_&_Sons dbpedia-fr:Oxford_University_Press dbpedia-fr:Springer_Science+Business_Media American Mathematical Society (fr) Springer-Verlag (fr) CRC Press (fr) North-Holland (fr) Johns Hopkins University (fr) École polytechnique de Paris (fr) Librairie Arthème Fayard et Collège de France (fr) |
| dct:subject | category-fr:Graphe_géométrique category-fr:Géométrie_algorithmique category-fr:Polygone category-fr:Problème_algorithmique |
| rdfs:comment | En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit : « Quel est le nombre de gardiens nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? » (fr) |
| rdfs:label | Problem der Museumswächter (de) Problème de la galerie d'art (fr) Задача о картинной галерее (ru) Теорема галереї мистецтв (uk) 美术馆问题 (zh) |
| owl:sameAs | dbr:Art_gallery_problem dbpedia-commons:Category:Art_gallery_problem wikidata:Q2000090 dbpedia-ca:Problema_del_guarda_del_museu dbpedia-de:Problem_der_Museumswächter dbpedia-es:Problema_de_la_galería_de_arte dbpedia-fa:نگارخانه_هنری_(هندسه) dbpedia-fi:Taidemuseo-ongelma dbpedia-he:בעיית_הגלריה_לאמנות dbpedia-hu:Képtárprobléma dbpedia-nl:Kunstgalerijprobleem dbpedia-pt:Problema_da_galeria_de_arte dbpedia-ru:Задача_о_картинной_галерее dbpedia-sr:Проблем_уметничке_галерије dbpedia-uk:Теорема_галереї_мистецтв dbpedia-zh:美术馆问题 http://g.co/kg/m/052fw1 http://ma-graph.org/entity/175474100 |
| prov:wasDerivedFrom | wikipedia-fr:Problème_de_la_galerie_d'art?oldid=178673216&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Art_gallery_problem.svg wiki-commons:Special:FilePath/Triangulation_3-coloring.svg wiki-commons:Special:FilePath/Festung-freie-wächter.svg wiki-commons:Special:FilePath/Polyhedron_with_no_vertex_visible_from_center.png |
| foaf:isPrimaryTopicOf | wikipedia-fr:Problème_de_la_galerie_d'art |
| is dbo:wikiPageRedirects of | dbpedia-fr:Problème_du_musée |
| is dbo:wikiPageWikiLink of | dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Géométrie_algorithmique dbpedia-fr:Raisonnements_divins dbpedia-fr:Triangulation_d'un_polygone dbpedia-fr:Victor_Klee dbpedia-fr:Maria_Klawe dbpedia-fr:Problème_du_musée |
| is oa:hasTarget of | tag-fr:UkFrResource tag-fr:DeFrResource tag-fr:RuFrResource tag-fr:ZhFrResource tag-fr:WdtFrResource |
| is foaf:primaryTopic of | wikipedia-fr:Problème_de_la_galerie_d'art |
