This HTML5 document contains 349 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n13http://www.inf.ethz.ch/personal/eidenben/publications/
dbpedia-fihttp://fi.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
n8http://fr.dbpedia.org/resource/Modèle:
dbpedia-hehttp://he.dbpedia.org/resource/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
n27http://cgm.cs.mcgill.ca/~godfried/publications/
dcthttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n38http://g.co/kg/m/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n24https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/
n16http://www.cs.ubc.ca/nest/theory/thread/papers/
n17http://drops.dagstuhl.de/opus/volltexte/2017/7215/
n33http://fr.dbpedia.org/resource/Fichier:
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/
dbpedia-ukhttp://uk.dbpedia.org/resource/
n5http://ma-graph.org/entity/
prop-frhttp://fr.dbpedia.org/property/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
n18https://books.google.com/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
n21http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/
n28http://commons.dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
n12http://www.cs.uu.nl/geobook/
n22http://liseuse-hachette.fr/file/
n14http://www.enseignement.polytechnique.fr/informatique/INF562/Notes/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
wikipedia-frhttp://fr.wikipedia.org/wiki/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbpedia-fr:Problème_de_la_galerie_d'art
rdfs:label
Задача о картинной галерее 美术馆问题 Теорема галереї мистецтв Problème de la galerie d'art Problem der Museumswächter
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 ? »
owl:sameAs
n5:175474100 wikidata:Q2000090 dbpedia-sr:Проблем_уметничке_галерије dbpedia-uk:Теорема_галереї_мистецтв dbpedia-he:בעיית_הגלריה_לאמנות n28:Art_gallery_problem dbr:Art_gallery_problem dbpedia-fi:Taidemuseo-ongelma dbpedia-ca:Problema_del_guarda_del_museu dbpedia-hu:Képtárprobléma dbpedia-de:Problem_der_Museumswächter dbpedia-es:Problema_de_la_galería_de_arte n38:052fw1 dbpedia-pt:Problema_da_galeria_de_arte dbpedia-nl:Kunstgalerijprobleem dbpedia-ru:Задача_о_картинной_галерее dbpedia-zh:美术馆问题 dbpedia-fa:نگارخانه_هنری_(هندسه)
dbo:wikiPageID
11387313
dbo:wikiPageRevisionID
178673216
dbo:wikiPageWikiLink
dbpedia-fr:Galerie_d'art dbpedia-fr:Problème_de_décision dbpedia-fr:Problème_de_couverture_par_ensembles dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Dimension_de_Vapnik-Chervonenkis dbpedia-fr:John_Wiley_&_Sons dbpedia-fr:Anna_Lubiw dbpedia-fr:NP-difficile dbpedia-fr:Polyèdre dbpedia-fr:Enveloppe_convexe dbpedia-fr:Majorant_ou_minorant category-fr:Polygone category-fr:Problème_algorithmique dbpedia-fr:Algorithme_d'approximation dbpedia-fr:Nombre_de_Catalan dbpedia-fr:Springer_Science+Business_Media dbpedia-fr:Coloration_de_graphe dbpedia-fr:APX_(complexité) dbpedia-fr:Bowdoin_College dbpedia-fr:Oxford_University_Press dbpedia-fr:Raisonnement_par_récurrence dbpedia-fr:Raisonnements_divins dbpedia-fr:Corps_réel_clos dbpedia-fr:Maria_Klawe dbpedia-fr:Jörg-Rüdiger_Sack dbpedia-fr:Segment_(mathématiques) dbpedia-fr:Václav_Chvátal dbpedia-fr:Daniel_Kleitman dbpedia-fr:Logarithme n33:Triangulation_3-coloring.svg dbpedia-fr:Bernard_Chazelle dbpedia-fr:Classe_de_complexité dbpedia-fr:Complexité_en_temps dbpedia-fr:Mark_Overmars dbpedia-fr:Géométrie_algorithmique n33:Art_gallery_problem.svg dbpedia-fr:Informatique dbpedia-fr:Cambridge_University_Press dbpedia-fr:Triangulation_d'un_polygone dbpedia-fr:Triangulation_de_Delaunay category-fr:Géométrie_algorithmique dbpedia-fr:Triangulation_d'un_ensemble_de_points n33:Festung-freie-wächter.svg dbpedia-fr:Conférences_WADS_et_SWAT dbpedia-fr:Diviser_pour_régner_(informatique) dbpedia-fr:Polygone_simple dbpedia-fr:Théorie_existentielle_sur_les_réels dbpedia-fr:Diagramme_de_Voronoï n33:Polyhedron_with_no_vertex_visible_from_center.png dbpedia-fr:Victor_Klee category-fr:Graphe_géométrique dbpedia-fr:Point_(géométrie) dbpedia-fr:Kurt_Mehlhorn
dbo:wikiPageExternalLink
n12: n17: n18:books%3Fid=Q2aXZl3fgvMC&printsec=frontcover n13:eidenbenz_algorithmica2001.pdf n22:43055 n27:star.pdf n14:Poly_INF562.pdf n16:shermer2002.pdf n24:eidenbenz_algorithmica2001.pdf n15:art.html n21: n18:books%3Fid=mxugg47mzK4C&printsec=frontcover n18:books%3Fid=vKT0BwAAQBAJ&printsec=frontcover
dbo:wikiPageLength
19866
dct:subject
category-fr:Géométrie_algorithmique category-fr:Polygone category-fr:Problème_algorithmique category-fr:Graphe_géométrique
prop-fr:wikiPageUsesTemplate
n8:Lien n8:Portail n8:Références n8:Sfn n8:Google_Livres n8:, n8:Harvsp n8:Article n8:Chapitre n8:Note n8:Ouvrage
prov:wasDerivedFrom
wikipedia-fr:Problème_de_la_galerie_d'art?oldid=178673216&ns=0
foaf:depiction
n10:Art_gallery_problem.svg n10:Polyhedron_with_no_vertex_visible_from_center.png n10:Triangulation_3-coloring.svg n10:Festung-freie-wächter.svg
prop-fr:année
1983 1981 1978 1975 2012 2010 2011 2008 2009 2007 2004 2001 1998 1999 1995 1992 1988 1986 1987 1984 1985 2017
prop-fr:arxiv
1704.07 1607.06
prop-fr:auteur
Jean-Daniel Boissonnat Godfried T. Toussaint Otfried Cheong Anna Lubiw Ajay Deshpande dbpedia-fr:Mark_Overmars Steve Oudot Luca Castelli Aleardi Jörg-Rüdiger Sack Václav Chvátal Michael T. Goodrich Thomas Shermer Erik Demaine Daniel J. Kleitman A. K. Lin Mark de Berg Hervé Brönnimann Mikkel Abrahamsen Maria M. Klawe Stephan Eidenbenz János Pach Peter Widmayer Subir Kumar Ghosh Ali A. Kooshesh Bernard M. E. Moret Der-Tsai Lee Herbert Edelsbrunner Alok Aggarwal Jacob E. Goodman Godfried Toussaint Anna Adamaszek Stefan Naeher Pankaj K. Agarwal Tillmann Miltzow David Avis Sanjay E. Sarma Steve Fisk Édouard Bonnet Pavel Valtr Joseph O'Rourke dbpedia-fr:Kurt_Mehlhorn Christoph Stamm Marc van Kreveld Micha Sharir Taejung Kim J. Kahn
prop-fr:auteurOuvrage
Godfried Toussaint
prop-fr:collection
Mathematical Surveys and Monographs EATCS Monographs on Theoretical Computer Science Cours INF562
prop-fr:consultéLe
2018-01-12
prop-fr:doi
10.1145 10.1109 10.1137 10.1111 10.1007 10.1016
prop-fr:fr
Godfried Toussaint Couverture d'un polygone ε-réseau Polygone anthropomorphe
prop-fr:id
CRSb CRSa
prop-fr:isbn
978 0 1 3
prop-fr:journal
Pattern Recognition Proceedings of the IEEE preprint Israel J. Math. IEEE Transactions on Information Theory Journal of Combinatorial Theory, Series B International Transactions in Operational Research SIAM J. Alg. Disc. Meth. Algorithmica Discrete and Computational Geometry Symposium on Computational Geometry Discrete Applied Mathematics
prop-fr:langue
en fr
prop-fr:lienAuteur
Maria Klawe
prop-fr:lieu
Berlin/Heidelberg/Paris etc. New York/Chichester/Brisbane etc. Providence, R.I. Cambridge Paris
prop-fr:lireEnLigne
n14:Poly_INF562.pdf n15:art.html n21: n18:books%3Fid=vKT0BwAAQBAJ&printsec=frontcover n18:books%3Fid=Q2aXZl3fgvMC&printsec=frontcover n22:43055 n18:books%3Fid=mxugg47mzK4C&printsec=frontcover
prop-fr:nom
de Rezende Couto de Souza
prop-fr:numéro
9 6 4 2 3 1
prop-fr:page
443 374
prop-fr:pages
425 395 79 39 718 1 20 194 276 1384 463
prop-fr:pagesTotales
423 386 123 73 235 354 1018
prop-fr:passage
97 45 163 153
prop-fr:prénom
Marcelo C. Cid C. Pedro J.
prop-fr:présentationEnLigne
n12:
prop-fr:responsabilité
éditeurs
prop-fr:sousTitre
algorithms and applications Leçon inaugurale du cours The Alcala Lectures
prop-fr:texte
ε-réseaux
prop-fr:titre
Guard placement in rectilinear polygons Decomposing polygonal regions into convex quadrilaterals Art Gallery Theorems and Algorithms Traditional galleries require fewer watchmen Introduction à la géométrie algorithmique et ses applications Recent Results in Art Galleries Three-coloring the vertices of a triangulated simple polygon A short proof of Chvátal's watchman theorem LEDA, A Platform for Combinatorial and Geometric Computing Inapproximability results for guarding polygons and terrains The Handbook of Discrete and Computational Geometry Combinatorial Geometry and its Algorithmic Applications Algorithms in Combinatorial Geometry Guarding galleries where no point sees a small area Combinatorial Geometry Almost optimal set covers in finite VC-dimension A combinatorial theorem in plane geometry An Approximation Algorithm for the Art Gallery Problem An efficient algorithm for decomposing a polygon into star-shaped polygons Benchmark instances for the art gallery problem with vertex guards The Art Gallery Problem is -complete Géométrie algorithmique : des données géométriques à la géométrie des données Computational complexity of art gallery problems A Pseudopolynomial Time O-Approximation Algorithm for Art Gallery Problems Approximation algorithms for art gallery problems in polygons The art gallery theorem : Its variations, applications, and algorithmic aspects Computational geometry An exact algorithm for minimizing vertex guards on art galleries
prop-fr:titreChapitre
Polygon Triangulation
prop-fr:titreOuvrage
dbpedia-fr:Conférences_WADS_et_SWAT Proc. 1st ACM Symposium on Computational Geometry Computational Morphology
prop-fr:trad
Ε-net Anthropomorphic polygon Polygon covering
prop-fr:url
n13:eidenbenz_algorithmica2001.pdf n16:shermer2002.pdf n27:star.pdf n17:
prop-fr:volume
158 13 14 4 31 24 25 18 32 80 104
prop-fr:éditeur
Librairie Arthème Fayard et Collège de France dbpedia-fr:John_Wiley_&_Sons Johns Hopkins University Springer-Verlag École polytechnique de Paris CRC Press dbpedia-fr:Springer_Science+Business_Media American Mathematical Society dbpedia-fr:Oxford_University_Press North-Holland dbpedia-fr:Cambridge_University_Press
prop-fr:numéroArticle
20
prop-fr:numéroD'édition
2 3
prop-fr:archivedate
2003-06-24
prop-fr:archiveurl
n24:eidenbenz_algorithmica2001.pdf
prop-fr:natureOuvrage
thèse Ph. D.
prop-fr:numéroChapitre
3
prop-fr:numéroDansCollection
152 4619 10
prop-fr:series
Lecture Notes in Computer Science
dbo:thumbnail
n10:Triangulation_3-coloring.svg?width=300
prop-fr:articleNuméro
20
foaf:isPrimaryTopicOf
wikipedia-fr:Problème_de_la_galerie_d'art
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.