Visibility problems appear in a variety of applicative backgrounds. While the traditional "art gallery" problem, which consists of guarding a given floorplan of an art gallery by a minimum number of guards seems to be mainly of theoretical interest, a variation of this problem, where a 2.5 dimensional terrain rather than a two dimensional polygonal floorplan needs to be guarded, is of practical significance in the planning of wireless communication networks, where minimizing the numbers of antennas reduces overall costs.
In a visibility problem, we are given an input polygon, which may or may not contain holes, or a 2.5 dimensional triangulated terrain. Since a lot of visibility problems are NP-hard, we study the approximation characteristics of these problems. In the talk, an overview of recent inapproximability as well as approximability results will be presented for a variety of NP-hard visibility problems:
We will discuss an inapproximability result for at least one of these problems in more detail, which should give a general idea of how to prove inapproximability of visibility problems. Finally, an approximation algorithm for a visibility problem will be presented.
(Host: Renato Pajarola, pajarola@acm.org.)