Name
Abstract | ||
|---|---|---|
We model the problem of detecting intruders using a set of infrared beams by the perimeter defense problem: given a polygon P, find a minimum set of edges S of the polygon such that any straight line segment crossing the polygon intersects at least one of the edges in S. We observe that this problem is equivalent to a new hiding problem, the Max-Hidden-Edge-Set problem. We prove the APX-hardness of the Max-Hidden-Edge-Set problem for polygons without holes and rectilinear polygons without holes, by providing gap-preserving reductions from the Max-5-Occurrence-2-Sat problem. |
Year | Venue | Keywords |
|---|---|---|
2009 | CCCG | infrared |
Field | DocType | Citations |
Art gallery problem,Discrete mathematics,Rectilinear polygon,Polygon,Combinatorics,Midpoint polygon,Polygon covering,Computer science,Regular polygon,Point in polygon,Star-shaped polygon | Conference | 4 |
PageRank | References | Authors |
0.57 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evangelos Kranakis | 1 | 3107 | 354.48 |
| Danny Krizanc | 2 | 1778 | 191.04 |
| Lata Narayanan | 3 | 613 | 62.78 |
| Kun Xu | 4 | 21 | 4.37 |