Das Problem der traditionellen Kunstgalerie richtet eine Region und Wachen mit einer gewissen Sichtbarkeit ein und fordert die Mindestanzahl von Wachen an, die platziert werden müssen, um die gesamte Region zu sehen.
Hat sich jemals jemand Kunstgalerievarianten angesehen, bei denen der Sichtbarkeitsbereich stattdessen von zwei Wachen definiert wird ? Zum Beispiel könnte eine Formulierung sein, dass ein Punkt abgedeckt wird, wenn es ein Paar von Schutzvorrichtungen gibt, deren minimale Begrenzungsscheibe ihn abdeckt?
reference-request
cg.comp-geom
Suresh Venkat
quelle
quelle
Antworten:
Mir ist eine solche Arbeit nicht bekannt. Ich würde jedoch erwarten, dass ein solches Problem NP-vollständig ist und für Polygone mit Löchern genauso schwer zu approximieren ist wie Set Cover. Das relativ einfache Problem der Vertex / Vertex-Bewachung, bei dem Wachen nur auf Scheitelpunkten liegen können und nur Scheitelpunkte geschützt werden müssen, ist so schwierig ( Eidenbenz, Stamm und Widmayer (2001) ).
Für einfache Polygone erwarte ich ein solches Problem:
Das Vertex / Vertex-Schutzproblem ist für einfache Polygone APX-schwer ( Eidenbenz (1998) ).
Ich habe in meiner Diplomarbeit ein wenig über dieses Problem nachgedacht, bin jedoch zu dem Schluss gekommen, dass es keine besonders interessanten Varianten gibt, die sich nicht ziemlich genau auf ein bekanntes Problem der Einzelwache zu beschränken scheinen.
quelle
Eher zu spät zu dieser Frage (sorry!). Es gibt zumindest ein bisschen Arbeit.
(1) Dies scheint ein Forschungsbericht für Studenten (Swarthmore) zu sein: "Optimale doppelte Abdeckung in der Kunstgalerie", Scott Dalane, Andrew Frampton, 2008, PDF-Link . Aus ihrer Schlussfolgerung:
quelle