Art gallery problem (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (ca) 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. (de) 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. (en) 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. (es) 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. (fr) 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. (nl) 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. (pt) Задача о картинной галерее или музейная задача — это хорошо изученная (просматриваемости) в вычислительной геометрии. Задача возникает в реальном мире как задача охраны художественной галереи минимальным числом охранников, которые в состоянии видеть всю галерею. В версии задачи для вычислительной геометрии галерея представляется как простой многоугольник, а каждый охранник представляется точкой внутри многоугольника. Говорят, что множество точек охраняет многоугольник, если для любой точки внутри многоугольника существует такая точка , что отрезок, соединяющий и , лежит полностью внутри многоугольника. (ru) Теорема галереї мистецтв або музейна проблема — добре вивчена проблема видності в обчислювальній геометрії. Вона походить від реальної задачі охорони художньої галереї за допомогою найменшої можливої кількості камер, що можуть одночасно спостерігати за всією галереєю. В обчислювальній геометрії планування галереї описується за допомогою простого многокутника і кожна камера представлена точкою у многокутнику. Кажуть, що множина точок охороняє многокутник, якщо для кожної точки у многокутнику існує деяка точка така, що відрізок між і не залишає цей многокутник. (uk) 美术馆问题或博物馆问题是计算几何中的一种, 来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中. 在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集 能够守卫一个多边形, 如果对多边形内的每个点 ,存在点 使得连接 和 的 线段 在多边形的内部. (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Art_gallery_problem.svg?width=300 |
| dbo:wikiPageExternalLink | 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 https://web.archive.org/web/20030624032504/http:/www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf http://www.cs.ubc.ca/nest/theory/thread/papers/shermer2002.pdf |
| dbo:wikiPageID | 1448859 (xsd:integer) |
| dbo:wikiPageLength | 23272 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124771943 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robotics dbr:Bernard_Chazelle dbr:Anna_Lubiw dbc:Polygons dbr:Approximation_algorithm dbr:Undirected_graph dbr:Upper_bound dbr:Victor_Klee dbr:Decision_problem dbr:Ε-net_(computational_geometry) dbr:Line_segment dbr:Polyhedron dbc:Articles_containing_proofs dbr:Mathematical_induction dbr:SWAT_and_WADS_conferences dbr:Graph_coloring dbr:NP-hard dbr:Linear_time dbr:Logarithm dbr:Computational_geometry dbr:Point_(geometry) dbr:Simple_polygon dbr:Tree_(graph_theory) dbr:Václav_Chvátal dbr:Jörg-Rüdiger_Sack dbc:Computational_geometry dbr:Dual_graph dbr:Daniel_Kleitman dbr:Godfried_Toussaint dbr:Graph_theory dbr:Israel_Journal_of_Mathematics dbr:Artificial_intelligence dbr:Polygon_triangulation dbr:Proofs_from_THE_BOOK dbr:Divide_and_conquer_algorithm dbr:Art_gallery dbc:Covering_problems dbr:Maria_Klawe dbr:Polygon_covering dbr:Polynomial-time_approximation_scheme dbr:Polynomial_time dbr:Approximation_ratio dbr:Dominating_set_problem dbr:VC_dimension dbr:Illumination_problem dbr:Image_editing dbr:Existential_theory_of_the_reals dbr:Visibility_graph dbr:Star-shaped_polygon dbr:Orthogonal_polygons dbr:Set_cover dbr:Visibility_problem 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 |
| 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:Center dbt:Citation dbt:Clear dbt:Efn dbt:Harvtxt dbt:Notelist dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Harvs dbt:PanoViewer |
| dbp:year | 1981 (xsd:integer) |
| dcterms:subject | dbc:Polygons dbc:Articles_containing_proofs dbc:Computational_geometry dbc:Covering_problems |
| rdf:type | yago:WikicatComputationalProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720 |
| rdfs:comment | 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. (ca) Задача о картинной галерее или музейная задача — это хорошо изученная (просматриваемости) в вычислительной геометрии. Задача возникает в реальном мире как задача охраны художественной галереи минимальным числом охранников, которые в состоянии видеть всю галерею. В версии задачи для вычислительной геометрии галерея представляется как простой многоугольник, а каждый охранник представляется точкой внутри многоугольника. Говорят, что множество точек охраняет многоугольник, если для любой точки внутри многоугольника существует такая точка , что отрезок, соединяющий и , лежит полностью внутри многоугольника. (ru) Теорема галереї мистецтв або музейна проблема — добре вивчена проблема видності в обчислювальній геометрії. Вона походить від реальної задачі охорони художньої галереї за допомогою найменшої можливої кількості камер, що можуть одночасно спостерігати за всією галереєю. В обчислювальній геометрії планування галереї описується за допомогою простого многокутника і кожна камера представлена точкою у многокутнику. Кажуть, що множина точок охороняє многокутник, якщо для кожної точки у многокутнику існує деяка точка така, що відрізок між і не залишає цей многокутник. (uk) 美术馆问题或博物馆问题是计算几何中的一种, 来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中. 在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集 能够守卫一个多边形, 如果对多边形内的每个点 ,存在点 使得连接 和 的 线段 在多边形的内部. (zh) 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. (en) 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. (de) 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. (es) 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 ? » (fr) 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. (nl) 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 (pt) |
| rdfs:label | Problema del guarda del museu (ca) Problem der Museumswächter (de) Problema de la galería de arte (es) Art gallery problem (en) Problème de la galerie d'art (fr) Kunstgalerijprobleem (nl) Problema da galeria de arte (pt) Задача о картинной галерее (ru) 美术馆问题 (zh) Теорема галереї мистецтв (uk) |
| owl:sameAs | freebase:Art gallery problem yago-res:Art gallery problem wikidata:Art gallery problem dbpedia-ca:Art gallery problem dbpedia-de:Art gallery problem dbpedia-es:Art gallery problem dbpedia-fa:Art gallery problem dbpedia-fi:Art gallery problem dbpedia-fr:Art gallery problem dbpedia-he:Art gallery problem dbpedia-hu:Art gallery problem dbpedia-nl:Art gallery problem dbpedia-pt:Art gallery problem dbpedia-ro:Art gallery problem dbpedia-ru:Art gallery problem dbpedia-sr:Art gallery problem dbpedia-uk:Art gallery problem dbpedia-zh:Art gallery problem https://global.dbpedia.org/id/uBiZ |
| prov:wasDerivedFrom | wikipedia-en:Art_gallery_problem?oldid=1124771943&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3-coloring_of_the_polygon.png wiki-commons:Special:FilePath/Art_gallery_problem.svg wiki-commons:Special:FilePath/Least_color_of_3-coloration.png wiki-commons:Special:FilePath/Orthogonal_polyhedron_with_no_vertex_visible_from_center.svg 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 wiki-commons:Special:FilePath/Triangulation_3-coloring.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Art_gallery_problem |
| is dbo:wikiPageRedirects of | dbr:Art_gallery_theorem 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_theorems dbr:Museum_guard_problem |
| is dbo:wikiPageWikiLink of | dbr:List_of_combinatorial_computational_geometry_topics dbr:Visibility_polygon dbr:Victor_Klee dbr:Chvátal dbr:Simple_polygon dbr:Fáry's_theorem dbr:Numbers_(season_2) dbr:Fan_triangulation dbr:Godfried_Toussaint dbr:Proofs_from_THE_BOOK dbr:Triangulation_(geometry) dbr:Watchman_route_problem dbr:Art_Gallery_Theorems_and_Algorithms dbr:Art_gallery_theorem dbr:Maria_Klawe dbr:Pigeonhole_principle dbr:Polygon_covering dbr:The_museum_problem dbr:Visibility_(geometry) dbr:Existential_theory_of_the_reals dbr:Visibility_graph 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_theorems dbr:Museum_guard_problem |
| is foaf:primaryTopic of | wikipedia-en:Art_gallery_problem |
