GUARDING TERRAINS VIA LOCAL SEARCH

Matt Gibson; Gaurav Kanade; Erik Krohn; Kasturi Varadarajan

doi:10.20382/jocg.v5i1a9

Back

Journal article

Open access

GUARDING TERRAINS VIA LOCAL SEARCH

Matt Gibson, Gaurav Kanade, Erik Krohn and Kasturi Varadarajan

Journal of computational geometry, Vol.5(1), pp.168-178

05/01/2014

DOI: 10.20382/jocg.v5i1a9

Files and links (1)

url

https://doi.org/10.20382/jocg.v5i1a9View

Published (Version of record) Open Access

Abstract

We obtain a polynomial time approximation scheme for the 1.5D 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 Ilar-Peled [3] and Mustafa and Ray [18]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.

Mathematics

Physical Sciences

Science & Technology

Details

Title: Subtitle: GUARDING TERRAINS VIA LOCAL SEARCH
Creators: Matt Gibson - Univ Texas San Antonio, Dept Comp Sci, San Antonio, TX 78249 USA
Gaurav Kanade - University of Wisconsin–Oshkosh
Erik Krohn - University of Wisconsin–Oshkosh
Kasturi Varadarajan - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
Resource Type: Journal article
Publication Details: Journal of computational geometry, Vol.5(1), pp.168-178
DOI: 10.20382/jocg.v5i1a9
ISSN: 1920-180X
eISSN: 1920-180X
Publisher: Carleton Univ, Dept Mathematics & Statistics
Number of pages: 11
Grant note: Faculty Development Grant from the University of Wisconsin - Oshkosh
Language: English
Date published: 05/01/2014
Academic Unit: Computer Science
Record Identifier: 9984410842602771

Metrics

19 Record Views

40 Times Cited - Web of Science