About: Art gallery problem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

Mathematical problem

Property	Value
dbo:description	mathematical problem (en) задача в вычислительной геометрии (ru) این مساله را در زمره مسائل هندسه محاسباتی قرار دارد (fa)
dbo:thumbnail	wiki-commons:Special:FilePath/Art_gallery_problem.svg?width=300
dbo:wikiPageExternalLink	https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/ http://cgm.cs.mcgill.ca/~godfried/publications/star.pdf http://www.cs.ubc.ca/nest/theory/thread/papers/shermer2002.pdf
dbo:wikiPageWikiLink	dbc:Articles_containing_proofs dbr:Image_editing dbr:Tree_(graph_theory) dbr:Undirected_graph dbc:Covering_problems dbr:Dual_graph dbr:Artificial_intelligence dbr:Logarithm dbr:Maria_Klawe dbr:Robotics dbr:Line_segment dbr:SWAT_and_WADS_conferences dbr:Illumination_problem dbc:Computational_geometry dbr:Computational_geometry dbr:Proofs_from_THE_BOOK dbr:Jörg-Rüdiger_Sack dbr:Art_gallery dbr:Existential_theory_of_the_reals dbr:Israel_Journal_of_Mathematics dbr:Star-shaped_polygon dbr:Graph_theory dbr:Mathematical_induction dbr:Graph_coloring dbc:Polygons dbr:Point_(geometry) dbr:Václav_Chvátal dbr:Polygon_triangulation dbr:Approximation_algorithm dbr:Victor_Klee dbr:Polynomial-time_approximation_scheme dbr:Polyhedron dbr:Bernard_Chazelle dbr:Daniel_Kleitman dbr:Simple_polygon dbr:Visibility_graph dbr:Godfried_Toussaint dbr:Decision_problem dbr:Polygon_covering dbr:Ε-net_(computational_geometry) dbr:Anna_Lubiw dbr:NP-hard dbr:Polynomial_time dbr:Linear_time dbr:Upper_bound dbr:VC_dimension dbr:File:Art_gallery_problem.svg dbr:File:Orthogonal_polyhedron_with_no_vertex_visible_from_center.svg dbr:File:Polyhedron_with_no_vertex_visible_from_center.svg dbr:File:Triangulation_3-coloring.svg dbr:Set_cover dbr:Orthogonal_polygons dbr:Divide_and_conquer_algorithm dbr:Dominating_set_problem dbr:Approximation_ratio dbr:Visibility_problem
dbp:author1Link	David Avis (en)
dbp:author2Link	Godfried Toussaint (en)
dbp:first	David (en) Godfried (en)
dbp:last	Toussaint (en) Avis (en)
dbp:wikiPageUsesTemplate	dbt:PanoViewer dbt:Reflist dbt:Notelist dbt:Citation dbt:Refend dbt:Sfnp dbt:Refbegin dbt:Harvs dbt:Harvtxt dbt:Efn dbt:Short_description
dbp:year	1981 (xsd:integer)
dct:subject	dbc:Articles_containing_proofs dbc:Covering_problems dbc:Computational_geometry dbc:Polygons
rdfs:label	Art gallery problem (en) Problema del guarda del museu (ca) Problema de la galería de arte (es) Problem der Museumswächter (de) Problème de la galerie d'art (fr) Kunstgalerijprobleem (nl) Problema da galeria de arte (pt) Задача о картинной галерее (ru) Теорема галереї мистецтв (uk) 美术馆问题 (zh)
owl:sameAs	freebase:Art gallery problem yago-res:Art gallery problem wikidata:Art gallery problem dbpedia-nl:Art gallery problem dbpedia-de:Art gallery problem dbpedia-fr:Art gallery problem dbpedia-zh:Art gallery problem dbpedia-pt:Art gallery problem dbpedia-he:Art gallery problem dbpedia-ro:Art gallery problem dbpedia-es:Art gallery problem dbpedia-hu:Art gallery problem dbpedia-fa:Art gallery problem dbpedia-ru:Art gallery problem dbpedia-ca:Art gallery problem dbpedia-fi:Art gallery problem dbpedia-sr:Art gallery problem dbpedia-uk:Art gallery problem dbpedia-global:Art gallery problem dbr:Art gallery problem
prov:wasDerivedFrom	wikipedia-en:Art_gallery_problem?oldid=1245494280&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Triangulation_3-coloring.svg wiki-commons:Special:FilePath/Orthogonal_polyhedron_with_no_vertex_visible_from_center.svg wiki-commons:Special:FilePath/Art_gallery_problem.svg wiki-commons:Special:FilePath/3-coloring_of_the_polygon.png wiki-commons:Special:FilePath/Least_color_of_3-coloration.png wiki-commons:Special:FilePath/Polyhedron_with_no_vertex_visible_from_center.svg wiki-commons:Special:FilePath/Polyhedron_with_no_ve...ble_from_center_(inside_panorama).jpg wiki-commons:Special:FilePath/Triangulation_of_polygon.png
foaf:isPrimaryTopicOf	wikipedia-en:Art_gallery_problem
is dbo:wikiPageRedirects of	dbr:Museum_guard_problem dbr:The_museum_problem dbr:Chvatal's_art_gallery_theorem dbr:Chvatal_art_gallery_theorem dbr:Chvátal's_art_gallery_theorem dbr:Chvátal_art_gallery_theorem dbr:Art_gallery_theorem dbr:Art_gallery_theorems
is dbo:wikiPageWikiLink of	dbr:List_of_combinatorial_computational_geometry_topics dbr:Maria_Klawe dbr:Chvátal dbr:Proofs_from_THE_BOOK dbr:Triangulation_(geometry) dbr:Fáry's_theorem dbr:Visibility_(geometry) dbr:Existential_theory_of_the_reals dbr:Pigeonhole_principle dbr:Victor_Klee dbr:Simple_polygon dbr:Visibility_graph dbr:Godfried_Toussaint dbr:Polygon_covering dbr:Art_Gallery_Theorems_and_Algorithms dbr:Visibility_polygon dbr:Watchman_route_problem dbr:Fan_triangulation dbr:Numbers_(season_2) dbr:Museum_guard_problem dbr:The_museum_problem dbr:Chvatal's_art_gallery_theorem dbr:Chvatal_art_gallery_theorem dbr:Chvátal's_art_gallery_theorem dbr:Chvátal_art_gallery_theorem dbr:Art_gallery_theorem dbr:Art_gallery_theorems
is foaf:primaryTopic of	wikipedia-en:Art_gallery_problem