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

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

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
n23http://www.inf.ethz.ch/personal/eidenben/publications/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-fihttp://fi.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n17http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
n39http://cgm.cs.mcgill.ca/~godfried/publications/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n30https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/
n13http://www.cs.ubc.ca/nest/theory/thread/papers/
n21http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
n15http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-rohttp://ro.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
yago-reshttp://yago-knowledge.org/resource/
n32https://global.dbpedia.org/id/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Art_gallery_problem
rdf:type
yago:Abstraction100002137 yago:Procedure101023820 yago:Condition113920835 yago:WikicatComputationalProblems yago:Rule105846932 yago:WikicatGeometricAlgorithms yago:State100024720 yago:Event100029378 yago:Difficulty114408086 yago:YagoPermanentlyLocatedEntity yago:Algorithm105847438 yago:PsychologicalFeature100023100 yago:Attribute100024264 yago:Problem114410605 yago:Act100030358 yago:Activity100407535
rdfs:label
Kunstgalerijprobleem Problème de la galerie d'art Problem der Museumswächter Problema de la galería de arte Задача о картинной галерее 美术馆问题 Problema del guarda del museu Problema da galeria de arte Art gallery problem Теорема галереї мистецтв
rdfs:comment
Теорема галереї мистецтв або музейна проблема — добре вивчена проблема видності в обчислювальній геометрії. Вона походить від реальної задачі охорони художньої галереї за допомогою найменшої можливої кількості камер, що можуть одночасно спостерігати за всією галереєю. В обчислювальній геометрії планування галереї описується за допомогою простого многокутника і кожна камера представлена точкою у многокутнику. Кажуть, що множина точок охороняє многокутник, якщо для кожної точки у многокутнику існує деяка точка така, що відрізок між і не залишає цей многокутник. O problema da galeria de arte (também conhecido como o problema do museu) é um bem estudado em geometria computacional, que tem a sua origem no seguinte problema do mundo real: "Numa galeria de arte de forma poligonal, qual é o número mínimo de guardas que juntos podem observar toda a galeria de arte"? Formalmente, considere uma área poligonal , interpretada como a planta de uma galeria de arte. Escolher o menor número possível de pontos (guardas) em tal que para cada ponto em , e para um o segmento de linha entre e não deixa o polígono. * Configuração 1 * Configuração 2 * Configuração 3 Задача о картинной галерее или музейная задача — это хорошо изученная (просматриваемости) в вычислительной геометрии. Задача возникает в реальном мире как задача охраны художественной галереи минимальным числом охранников, которые в состоянии видеть всю галерею. В версии задачи для вычислительной геометрии галерея представляется как простой многоугольник, а каждый охранник представляется точкой внутри многоугольника. Говорят, что множество точек охраняет многоугольник, если для любой точки внутри многоугольника существует такая точка , что отрезок, соединяющий и , лежит полностью внутри многоугольника. El problema del guarda del museu és un 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 de punts guarda un polígon si, per tot punt del polígon hi ha algun pertanyent a tal que la línia entre i no surti del polígon. 美术馆问题或博物馆问题是计算几何中的一种, 来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中. 在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集 能够守卫一个多边形, 如果对多边形内的每个点 ,存在点 使得连接 和 的 线段 在多边形的内部. Das Problem der Museumswächter (en: Art gallery problem) ist eine Fragestellung der algorithmischen Geometrie. Dabei wird folgende Situation untersucht: „Gegeben sei eine polygonale Fläche mit Rand , interpretiert als Grundriss eines Museums. Wähle nun möglichst wenige Punkte (‚Wächter‘) im Innern des Polygons, sodass jeder Punkt im Innern des Polygons durch eine Gerade, die ganz in einschließlich Rand liegt, mit einem Wächter verbunden werden kann.“ Das ist äquivalent dazu, ein Polygon minimal sternförmig zu überdecken. 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 (ou caméras) nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? » El problema de la galería de arte o problema del museo es un muy estudiado en la geometría computacional. La cuestión fue planteada por Victor Klee en 1973 en estos términos: Determinar el mínimo número de puntos de un polígono que son suficientes para ver a todos los restantes. Se puede interpretar también en términos de vigilancia de una sala poligonal. The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: "In an art gallery, what is the minimum number of guards who together can observe the whole gallery?" In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon. Het museumprobleem of kunstgalerijprobleem (Engels: art gallery problem) is een wiskundig probleem uit de computationele meetkunde: hoeveel suppoosten zijn er minimaal nodig om een kunstgalerij te bewaken, waarvan de plattegrond een eenvoudige veelhoek is? Elk punt in de galerij moet dus in het gezichtsveld van minstens een suppoost liggen. We veronderstellen dat de suppoosten stationair zijn en een gezichtsveld van 360° hebben.
foaf:depiction
n17:Least_color_of_3-coloration.png n17:Orthogonal_polyhedron_with_no_vertex_visible_from_center.svg n17:Polyhedron_with_no_vertex_visible_from_center.svg n17:Polyhedron_with_no_vertex_visible_from_center_(inside_panorama).jpg n17:Triangulation_3-coloring.svg n17:3-coloring_of_the_polygon.png n17:Art_gallery_problem.svg n17:Triangulation_of_polygon.png
dcterms:subject
dbc:Computational_geometry dbc:Covering_problems dbc:Polygons dbc:Articles_containing_proofs
dbo:wikiPageID
1448859
dbo:wikiPageRevisionID
1124771943
dbo:wikiPageWikiLink
dbc:Computational_geometry dbr:Undirected_graph dbr:Godfried_Toussaint dbr:Graph_theory dbr:Polygon_covering dbr:Existential_theory_of_the_reals dbr:Logarithm dbr:Computational_geometry dbr:Robotics dbr:NP-hard dbr:Star-shaped_polygon dbr:SWAT_and_WADS_conferences dbr:Maria_Klawe dbr:Mathematical_induction dbr:Václav_Chvátal dbr:Point_(geometry) n21:Triangulation_3-coloring.svg dbr:Visibility_problem dbr:Dual_graph dbr:Bernard_Chazelle dbr:Graph_coloring dbr:Orthogonal_polygons dbr:Dominating_set_problem dbr:Tree_(graph_theory) dbr:Anna_Lubiw n21:Art_gallery_problem.svg dbr:Decision_problem dbr:Ε-net_(computational_geometry) dbr:Polynomial-time_approximation_scheme dbr:Approximation_algorithm dbr:Polynomial_time dbr:VC_dimension dbr:Approximation_ratio dbr:Artificial_intelligence n21:Orthogonal_polyhedron_with_no_vertex_visible_from_center.svg dbr:Image_editing dbr:Proofs_from_THE_BOOK dbr:Line_segment dbc:Articles_containing_proofs dbr:Linear_time dbc:Covering_problems dbr:Illumination_problem n21:Polyhedron_with_no_vertex_visible_from_center.svg dbr:Upper_bound dbr:Visibility_graph dbr:Victor_Klee dbr:Polyhedron dbr:Daniel_Kleitman dbr:Simple_polygon dbc:Polygons dbr:Set_cover dbr:Israel_Journal_of_Mathematics dbr:Jörg-Rüdiger_Sack dbr:Divide_and_conquer_algorithm dbr:Polygon_triangulation dbr:Art_gallery
dbo:wikiPageExternalLink
n13:shermer2002.pdf n15: n23:eidenbenz_algorithmica2001.pdf n30:eidenbenz_algorithmica2001.pdf n39:star.pdf
owl:sameAs
dbpedia-sr:Проблем_уметничке_галерије dbpedia-pt:Problema_da_galeria_de_arte dbpedia-uk:Теорема_галереї_мистецтв dbpedia-nl:Kunstgalerijprobleem freebase:m.052fw1 wikidata:Q2000090 dbpedia-fa:نگارخانه_هنری_(هندسه) dbpedia-ru:Задача_о_картинной_галерее dbpedia-ro:Problema_galeriei_de_artă dbpedia-fi:Taidemuseo-ongelma dbpedia-he:בעיית_הגלריה_לאמנות yago-res:Art_gallery_problem dbpedia-hu:Képtárprobléma n32:uBiZ dbpedia-de:Problem_der_Museumswächter dbpedia-es:Problema_de_la_galería_de_arte dbpedia-zh:美术馆问题 dbpedia-fr:Problème_de_la_galerie_d'art dbpedia-ca:Problema_del_guarda_del_museu
dbp:wikiPageUsesTemplate
dbt:Harvtxt dbt:Reflist dbt:Harvs dbt:Refend dbt:Refbegin dbt:Center dbt:Sfnp dbt:Citation dbt:PanoViewer dbt:Notelist dbt:Short_description dbt:Clear dbt:Efn
dbo:thumbnail
n17:Art_gallery_problem.svg?width=300
dbp:first
David Godfried
dbp:last
Toussaint Avis
dbp:year
1981
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 (ou caméras) 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. Het museumprobleem of kunstgalerijprobleem (Engels: art gallery problem) is een wiskundig probleem uit de computationele meetkunde: hoeveel suppoosten zijn er minimaal nodig om een kunstgalerij te bewaken, waarvan de plattegrond een eenvoudige veelhoek is? Elk punt in de galerij moet dus in het gezichtsveld van minstens een suppoost liggen. We veronderstellen dat de suppoosten stationair zijn en een gezichtsveld van 360° hebben. Dit probleem en allerlei variaties erop zijn uitgebreid bestudeerd en in 1987 wijdde er zelfs een volledige monografie aan. formuleerde het probleem in de rand van een wetenschappelijk congres in 1973 als antwoord op een vraag van voor een interessant meetkundig probleem. Теорема галереї мистецтв або музейна проблема — добре вивчена проблема видності в обчислювальній геометрії. Вона походить від реальної задачі охорони художньої галереї за допомогою найменшої можливої кількості камер, що можуть одночасно спостерігати за всією галереєю. В обчислювальній геометрії планування галереї описується за допомогою простого многокутника і кожна камера представлена точкою у многокутнику. Кажуть, що множина точок охороняє многокутник, якщо для кожної точки у многокутнику існує деяка точка така, що відрізок між і не залишає цей многокутник. Задача о картинной галерее или музейная задача — это хорошо изученная (просматриваемости) в вычислительной геометрии. Задача возникает в реальном мире как задача охраны художественной галереи минимальным числом охранников, которые в состоянии видеть всю галерею. В версии задачи для вычислительной геометрии галерея представляется как простой многоугольник, а каждый охранник представляется точкой внутри многоугольника. Говорят, что множество точек охраняет многоугольник, если для любой точки внутри многоугольника существует такая точка , что отрезок, соединяющий и , лежит полностью внутри многоугольника. The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: "In an art gallery, what is the minimum number of guards who together can observe the whole gallery?" In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon. The art gallery problem can be applied in several domains such as in robotics, when artificial intelligences (AI) need to execute movements depending on their surroundings. Other domains, where this problem is applied, are in image editing, lighting problems of a stage or installation of infrastructures for the warning of natural disasters. Das Problem der Museumswächter (en: Art gallery problem) ist eine Fragestellung der algorithmischen Geometrie. Dabei wird folgende Situation untersucht: „Gegeben sei eine polygonale Fläche mit Rand , interpretiert als Grundriss eines Museums. Wähle nun möglichst wenige Punkte (‚Wächter‘) im Innern des Polygons, sodass jeder Punkt im Innern des Polygons durch eine Gerade, die ganz in einschließlich Rand liegt, mit einem Wächter verbunden werden kann.“ Das ist äquivalent dazu, ein Polygon minimal sternförmig zu überdecken. In der Praxis tritt das Problem in der Robotik auf, wenn „künstliche Intelligenzen“ Bewegungsmuster in Abhängigkeit von ihren Umgebungen ausführen sollen. Manche Fragestellungen der digitalen Bildbearbeitung lassen sich auf Wächterprobleme zurückführen. Auch Beleuchtungsprobleme einer Bühne und das Problem bei der Beobachtung von Tierpopulationen in großen Gebieten können als Wächterproblem modelliert werden. Eine weitere Anwendung ist die Aufstellung der Infrastruktur für die Wetterbeobachtung oder zur Warnung vor Naturkatastrophen. Das Problem fällt komplexitätstheoretisch in die Klasse der APX-Probleme, das heißt, dass wahrscheinlich kein Algorithmus existiert, der es für allgemeine Polygone effizient und korrekt löst. Andererseits hat man für das Problem und seine Varianten obere Schranken für die Zahl der Wächter gefunden und beweisen können, dass diese auch scharf sind. Das heißt, sie können nicht weiter verbessert werden, ohne dass man sich auf spezielle Polygonklassen einschränkt. Die wahrscheinlich erste systematische Betrachtung von Sichtbarkeitsfragen regte Victor Klee im August 1973 auf einer Konferenz in Stanford an, indem er das Museumsproblem für Punktwächter und eine sich als korrekt herausgestellte Vermutung formulierte. Zwei Jahre später präsentierte Chvátal eine bewiesene Lösung des Problems. El problema de la galería de arte o problema del museo es un muy estudiado en la geometría computacional. La cuestión fue planteada por Victor Klee en 1973 en estos términos: Determinar el mínimo número de puntos de un polígono que son suficientes para ver a todos los restantes. Se puede interpretar también en términos de vigilancia de una sala poligonal. La motivación de este problema se da porque las Galerías de Arte tienen que vigilar las costosas colecciones de pintores famosos de criminales que busquen robarlas. Estas galerías vigilan las colecciones con video cámaras durante las noches, se busca que el número de video cámaras sea lo más pequeño posible pero que cada parte de la galería pueda ser visible por al menos una de ellas. Por lo tanto, la colocación de las cámaras debe ser estratégica. ​ O problema da galeria de arte (também conhecido como o problema do museu) é um bem estudado em geometria computacional, que tem a sua origem no seguinte problema do mundo real: "Numa galeria de arte de forma poligonal, qual é o número mínimo de guardas que juntos podem observar toda a galeria de arte"? Formalmente, considere uma área poligonal , interpretada como a planta de uma galeria de arte. Escolher o menor número possível de pontos (guardas) em tal que para cada ponto em , e para um o segmento de linha entre e não deixa o polígono. Neste cenário, os guardas não são móveis e têm um campo visual de graus, de modo a poderem ser interpretados como câmaras de vigilância. * Configuração 1 * Configuração 2 * Configuração 3 O problema da galeria de arte pode ser aplicado em vários domínios, tais como na robótica, quando as inteligências artificiais (IA) precisam de executar movimentos dependendo do seu ambiente. Outros domínios, onde este problema é aplicado, são a edição de imagens, problemas de iluminação de um palco ou a instalação de infra-estruturas para a alerta de catástrofes naturais. El problema del guarda del museu és un 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 de punts guarda un polígon si, per tot punt del polígon hi ha algun pertanyent a tal que la línia entre i no surti del polígon. 美术馆问题或博物馆问题是计算几何中的一种, 来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中. 在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集 能够守卫一个多边形, 如果对多边形内的每个点 ,存在点 使得连接 和 的 线段 在多边形的内部.
dbp:author1Link
David Avis
dbp:author2Link
Godfried Toussaint
prov:wasDerivedFrom
wikipedia-en:Art_gallery_problem?oldid=1124771943&ns=0
dbo:wikiPageLength
23272
foaf:isPrimaryTopicOf
wikipedia-en:Art_gallery_problem