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 by vertex guards. 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 |
|---|---|---|
2006 | 10.1007/11785293_22 | SWAT |
Keywords | Field | DocType |
connection yield,minimum clique cover,rectilinear polygon,boundary guard,minimum line,rectilinear domain,vertex guard,known reduction,interesting connection,rectilinear terrain,minimum piercing,chordal graph | Discrete mathematics,Approximation algorithm,Combinatorics,Polygon,Rectilinear polygon,Vertex (geometry),Chordal graph,Clique cover,Mathematical proof,Clique (graph theory),Mathematics | Conference |
Volume | ISSN | ISBN |
4059 | 0302-9743 | 3-540-35753-X |
Citations | PageRank | References |
1 | 0.38 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew J. Katz | 1 | 225 | 19.92 |
| Gabriel S. Roisman | 2 | 24 | 1.60 |