Warianty galerii sztuki z widocznością parą?

Problem z tradycyjną galerią sztuki tworzy region i strażników z pewnym pojęciem widoczności i prosi o minimalną liczbę strażników, którzy muszą być umieszczeni, aby zobaczyć cały region.

Czy ktoś kiedykolwiek oglądał warianty galerii sztuki, w których obszar widoczności jest definiowany przez parę strażników. Na przykład, jedną z formuł może być to, że punkt jest objęty, jeśli istnieje para strażników, których minimalny dysk ograniczający go obejmuje?

reference-request cg.comp-geom

— Suresh Venkat
źródło

Quis custodiet ipsos custodes?

— Artem Kaznatcheev

Cóż, aby odpowiedzieć na pytanie @ Artema, istnieje pojęcie połączonych strażników , które ma dwa warianty. Niech wykres widoczności zostanie zdefiniowany z wierzchołkiem dla każdej osłony i krawędzią między dwoma wierzchołkami, jeśli strażnicy mogą się widzieć. Jeśli wykres widoczności jest połączony, wszyscy strażnicy są strzeżeni (czasami nazywani „zestawem strzeżonych strażników”). Silniejszym warunkiem jest to, że wykres widoczności ma jeden połączony komponent. Następnie masz zestaw połączonych strażników. I tak, tutaj jest sporo pracy. Napisałem nawet na blogu o jednym artykule.

— Aaron Sterling

Ups, powyższy tekst powinien brzmieć „jeśli wykres widoczności nie ma izolowanych wierzchołków, wszyscy strażnicy są strzeżeni ...”

— Aaron Sterling

„kto chroni strażników”? mój łacina to tylko świnia :)

— Suresh Venkat

Zauważ, że w moim sformułowaniu nie wymagam, aby wykres indukowanej widoczności był połączony. Chociaż może to nie być problem z prostokątami równoległymi do osi, może to być problem z regionami, które nie są tak ładne (jak regiony eliptyczne). Ale wskaźnik połączonych strażników jest dobry: myślę, że prawdopodobnie niektóre warianty mojego problemu można rozwiązać w ten sposób.

— Suresh Venkat

Odpowiedzi:

Nie znam żadnej takiej pracy. Spodziewałbym się jednak, że taki problem byłby NP-zupełny, a dla wielokątów z dziurami byłby tak trudny do oszacowania jak Zestaw Osłon. Stosunkowo prosty problem ochrony wierzchołków / wierzchołków, w którym strażnicy mogą leżeć tylko na wierzchołkach i tylko wierzchołki muszą być strzeżone, jest trudny ( Eidenbenz, Stamm i Widmayer (2001) ).

W przypadku prostych wielokątów spodziewam się, że takim problemem będzie:

NP-complete
Twardy APX
Przybliża się do współczynnika , gdzie opt jest optymalną liczbą strażników. $O(\log(\rm{opt}))$

Problem ochrony wierzchołków / wierzchołków jest trudny w APX dla prostych wielokątów ( Eidenbenz (1998) ).

Najlepsze algorytmy dla problemu galerii sztuki dla prostych wielokątów oparte są na budowaniu małych sieci . W prostych wielokątach przestrzenie zasięgu indukowane przez wielokąty widoczności mają stały wymiar VC. Kręgi też. Dlatego przestrzeń zasięgu indukowana przez wielokąty widoczności w prostym wielokącie, okręgach oraz ich przecięcia i połączenia również będą miały stały wymiar VC i można uzyskać algorytm aproksymacji . $\varepsilon$ $O(\log(\rm{opt}))$

Zastanawiałem się trochę nad tym problemem w mojej pracy magisterskiej, ale doszedłem do wniosku, że nie było żadnych szczególnie interesujących wariantów, które nie wydawałyby się dość zbliżone do znanego problemu polegającego na pojedynczej ochronie.

— James King
źródło

Raczej późno na to pytanie (przepraszam!). Jest co najmniej trochę pracy.

(1) Wydaje się, że jest to praca badawcza licencjata (Swarthmore): „Optimal Double Coverage In The Art Gallery”, Scott Dalane, Andrew Frampton, 2008, link PDF . Z ich wniosku:

Po przetestowaniu naszego algorytmu na coraz bardziej złożonych wielokątach, nasz algorytm z łatwością radzi sobie lepiej niż umieszczanie kamer w celu podwójnego pokrycia kamer poza najgorszym przypadkiem, podczas gdy cały program działa w czasie ... $\lfloor 2n/3 \rfloor$ $n^2$

(2) Znalazłem również niemiecki doktorat z 2007 r. rozprawa doktorska „Lokalizacja obiektu i problemy z tym związane” Martina Romaucha ( link PDF ), która zawiera rozdział dotyczący problemu podwójnej osłony Vertex Guard, pokazujący, że jest ona trudna do NP dla wielokątów z dziurami. Pokazuje także, że prawą kombinatoryczną granicą jest (rozczarowująco oczywiste!). Przeszedłem tylko przez to, ale z pewnością warto to zobaczyć. $\lfloor 2n/3 \rfloor$

— Joseph O'Rourke
źródło

Więc myślałem o tym. Myślę, że główna różnica między podwójnym pokryciem a moim problemem polega na tym, że występuje problem „łączności”. Innymi słowy, żaden z obszarów widoczności dwóch strażników nie zostanie aktywowany, chyba że będzie dla siebie „widoczny”. Łatwo jest skonstruować przykłady, w których można dwukrotnie osłonić region strażnikami, którzy się nie widzą. Teraz problem połączonych strażników został również rozpatrzony, ale w innym kontekście, który ponownie nie ma tutaj zastosowania - szczególnie tam, gdzie wymaga się podłączenia wykresu widoczności strażników, i nie potrzebuję tego.

— Suresh Venkat

@Suresh: Więc punkt jest objęty, jeśli istnieje para strażników, którzy (a) mogą się widzieć i (b) obaj widzą ? Próbuję tylko zrozumieć problematykę ...

p

$p$

p

$p$

— Joseph O'Rourke

Och, i (c) oba są „w zasięgu” ?

p

$p$

— Joseph O'Rourke,

Nie do końca. to nie jest czysta widoczność. Para strażników określa „obszar widoczności”, a punkt jest objęty, jeśli leży w obszarze widoczności strażników. W rzeczywistości strażnicy, którzy nie widzą się, LUB punkt w tradycyjnym „polu widzenia” mogą „zakryć” punkt.

— Suresh Venkat

Dzięki za wytłumaczenie. Ten model wydaje się inny niż wszystko, co wiem.

— Joseph O'Rourke,