Варианты художественной галереи с попарной видимостью?

Задача традиционной художественной галереи устанавливает регион и охранников с некоторым представлением о видимости и требует минимального количества охранников, которые необходимо разместить, чтобы увидеть весь регион.

Кто-нибудь когда-нибудь смотрел варианты художественной галереи, где область видимости определяется парой охранников? Например, одна формулировка может заключаться в том, что точка покрыта, если есть пара охранников, чей минимальный ограничивающий диск покрывает ее?

Я не знаю ни о какой такой работе. Тем не менее, я ожидаю, что такая проблема будет NP-полной и для полигонов с отверстиями будет так же трудно аппроксимировать, как Set Cover. Это относительно простая задача защиты вершин / вершин, в которой охранники могут лежать только на вершинах, а охранять нужно только вершины ( Eidenbenz, Stamm и Widmayer (2001) ).

Для простых полигонов, я ожидаю, что такая проблема будет:

• NP-полной
• APX-жесткий
• $O(\log(\rm{opt}))$

Задача защиты вершин / вершин является APX-сложной для простых полигонов ( Eidenbenz (1998) ).

$\varepsilon$$O(\log(\rm{opt}))$

Я немного подумал об этой проблеме для своего тезиса, но пришел к мнению, что не было никаких особенно интересных вариантов, которые, казалось бы, не сводились достаточно близко к известной проблеме, связанной с одиночной охраной.

Скорее опоздал на этот вопрос (извините!). Есть хоть немного работы.

(1) Это, по-видимому, исследовательская работа старшекурсника (Swarthmore): «Оптимальное двойное покрытие в художественной галерее», Скотт Далэйн, Эндрю Фрамптон, 2008, ссылка на PDF . Из их заключения:

$\lfloor 2n/3 \rfloor$$n^2$

$\lfloor 2n/3 \rfloor$