(In-)Approximability of visibility problems on polygons and terrains
Stephan Eidenbenz · Repository for Publications and Research Data (ETH Zurich) · 2000
Visibility problems appear in a variety of applicative backgrounds.While the traditional "art gallery" problem, which consists of guarding a given floor plan 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 floor plan 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 mayor may not contain holes, 01' a 2.5 dimensional triangulated terrain.We say that two points in the polygon 01' on 01' above the terrain see each other, if the straight line segment connecting the two points does not intersect the exterior of the polygon 01' the space below the terrain.A first category of visibility problems is the problem of "guarding" .We need to find a minimum number of guard positions, such that these guards collectively see the whole polygon 01' the terrain.Since this problem is N P-hard in most variations, the search for approximabilityas well as inapproximability results may prove helpful.We show that for input polygons with holes, no polynornial time approxirnation algorithm can achieve an approximation ratio that is logarithmic in the number of polygon vertices.This result is tight up to constant factors, since there exists a polynomial time algorithm that achieves a logarithmic approximation ratio.We obtain this result by construction a gap-preserving reduction from the MINIMUM SET COVER problem.This inapproximability result carries over to the problem of guarding tetrains.We also propose an approximation algorithm for guarding terrains that achieves a logarithmic approxirnation ratio.The situation is less clear for input polygons without holes: we are only able to show APX-hardness (i.e.there exists a constant e, such that no approximation algorithm can achieve an approximation ratio of 1 +f).We modify and analyze an already known reduction to obtain this result.Thus, for poly-