Guarding terrains via local search

Erik Krohn, Matt Gibson, Gaurav Kanade, Kasturi Varadarajan

Abstract


We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled (SoCG 2009) and Mustafa and Ray (DCG 2010). Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v5i1a9

ISSN: 1920-180X