Presentation
Guarding the vertices of thin orthogonal polygons is NP-hard
Author/s | Nunes Gomes Tomás, Ana Paula |
Editor | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Publication Date | 2013 |
Deposit Date | 2017-05-18 |
Published in |
|
Abstract | 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. |
Project ID. | PEst-C/MAT/UI0144/2011 |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Guarding the vertices of thin ... | 1.234Mb | [PDF] | View/ | |