Mezei Tamas Robert

	
Title: Mobile vs point guards

Abstract
Our results are concerned with art gallery theorems on orthogonal
polygons. We prove that an n-vertex orthogonal polygon can be
partitioned into (3n+4)/16 at most 8-vertex pieces. This directly
implies Aggarwal's theorem, namely that (3n+4)/16 mobile guards are
sufficient to control the interior of an n-vertex orthogonal polygon. 

Furthermore, we show that the cardinality of an optimal point guard of
the interior an orthogonal polygon P is bounded from above by a linear
function of the minimum number of horizontal mobile guards required to
control P, and the minimum number of vertical mobile guards required to
control P. Moreover, we construct an algorithm which computes the
latter two numbers in linear time. As a consequence, we can compute an
8/3-approximation of the size of an optimal point guard in linear time.