# ICS Department Seminar

## 24 March 2000, 11:00AM, CS 432:

(In-)Approximability of Visibility Problems in Polygons and
Terrains

Stephan Eidenbenz, ETH Zurich

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:

- guarding a polygon with or without holes or a terrain with a
minimum number of guards,
- hiding a maximum number of points from each other in a polygon
or a terrain, and
- covering a polygon with a minimum number of convex polygons
that lie inside the given polygon.

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.)