Ponencia
Guarding the vertices of thin orthogonal polygons is NP-hard
Autor/es | Nunes Gomes Tomás, Ana Paula |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-18 |
Publicado en |
|
Resumen | An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum ... An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum guard set for either a thin orthogonal polygon or only its vertices is NP-hard, indeed APX-hard, either for guards lying on the boundary or on vertices of the polygon. |
Identificador del proyecto | PEst-C/MAT/UI0144/2011 |
Cita | Nunes Gomes Tomás, A.P. (2013). Guarding the vertices of thin orthogonal polygons is NP-hard. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Guarding the vertices of thin ... | 1.234Mb | [PDF] | Ver/ | |