Name
Abstract | ||
|---|---|---|
We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover. We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.comgeo.2007.02.002 | Comput. Geom. |
Keywords | DocType | Volume |
connection yield,geometric optimization,minimum clique cover,boundary guard,rectilinear polygon,approximation algorithms,rectilinear terrain,np-hardness,minimum line,rectilinear domain,2-approximation algorithm,known reduction,guarding,interesting connection,minimum piercing,chordal graph | Journal | 39 |
Issue | ISSN | Citations |
3 | Computational Geometry: Theory and Applications | 23 |
PageRank | References | Authors |
1.22 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew J. Katz | 1 | 225 | 19.92 |
| Gabriel S. Roisman | 2 | 24 | 1.60 |