Algorithms Seminar: Bengt J. Nilsson
Date: May 18, 2006 (Thursday) at 14:15 to 15:00
Approximate Guarding of Monotone and Rectilinear Polygons
Bengt J. Nilsson (Malmö)
Abstract. We show a constant factor approximation algorithm for interior guarding of monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is \OPT\ for a rectilinear polygon, our algorithm produces a guard set of size~$O(\OPT^2)$.
Room: E:2405
Last modified Dec 9, 2011 12:59 pm
0924