A constant-factor approximation algorithm for optimal terrain guarding

Boaz Ben-Moshe; Matthew J. Katz; Joseph S.B. Mitchell

A constant-factor approximation algorithm for optimal terrain guarding

Boaz Ben-Moshe
, Matthew J. Katz
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Ben-Gurion University of the Negev

Research output: Contribution to conference › Paper › peer-review

30 Scopus citations

Abstract

We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.

Original language	English
Pages	515-524
Number of pages	10
State	Published - 2005
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005

Conference

Conference	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	01/23/05 → 01/25/05

Cite this

@conference{1cbd9985c6b84fdcb2f92afe43ccc6fb,

title = "A constant-factor approximation algorithm for optimal terrain guarding",

abstract = "We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.",

author = "Boaz Ben-Moshe and Katz, \{Matthew J.\} and Mitchell, \{Joseph S.B.\}",

year = "2005",

language = "English",

pages = "515--524",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - A constant-factor approximation algorithm for optimal terrain guarding

AU - Ben-Moshe, Boaz

AU - Katz, Matthew J.

AU - Mitchell, Joseph S.B.

PY - 2005

Y1 - 2005

N2 - We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.

AB - We present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.

UR - https://www.scopus.com/pages/publications/20744432163

M3 - Paper

AN - SCOPUS:20744432163

SP - 515

EP - 524

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

A constant-factor approximation algorithm for optimal terrain guarding

Abstract

Conference

Other files and links

Fingerprint

Cite this