E:2405

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