FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik

Vortrag des Informatik-Kolloquiums

Art gallery problems have received considerable attention in computational geometry - a whole book has been devoted to them. They address different aspects of the following theme: Given a polygonalregion, how many points (guards) are necessary to guard the whole polygon?

Sometimes, however, we find ourselve with the reverse problem. We are given a polygonal region, and a set of guards, and we would like to compute the region visible from all these guards.

We give tight upper and lower bounds on the complexity of this visible regions and show how the bound is used to analyze a simple algorithm to comput the region.