Guarding Terrains Via Local Search

Simple item page
dc.contributor.authorGibson, Matthew
dc.contributor.authorKanade, Gaurav
dc.contributor.authorKrohn, Erik
dc.contributor.authorVaradarajan, Kasturi
dc.date.accessioned2021-12-07T21:11:41Z
dc.date.available2021-12-07T21:11:41Z
dc.date.issued2014-05-30
dc.description.abstractWe 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.en_US
dc.description.departmentComputer Scienceen_US
dc.identifier.issn1920-180X
dc.identifier.urihttps://hdl.handle.net/20.500.12588/761
dc.language.isoen_USen_US
dc.relation.ispartofseriesJournal of Computational Geometry;Vol. 5 No. 1
dc.rightsAttribution 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/us/*
dc.titleGuarding Terrains Via Local Searchen_US
dc.typeArticleen_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
2931-Article PDF-7254-1-10-20210225.pdf
Size:
205.83 KB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

College of Sciences Faculty Research