Guarding thin orthogonal polygons is hard

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2013

Autores

Tomas, AP (Autor) FCUP

Ata de Conferência Internacional

Título: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Páginas: 305-316

19th International Symposium on Fundamentals of Computation Theory, FCT 2013

Liverpool, 19 August 2013 through 21 August 2013

Indexação

ISI Web of Knowledge

Scopus - 9 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Físicas > Ciência de computadores

Projetos Associados

PEst-C/MAT/UI0144/2013 - Projecto Estratégico - UI 144 - 2013-2014

Outras Informações

ID Authenticus: P-008-DDZ

DOI: 10.1007/978-3-642-40164-0_29

Abstract (EN): 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. For guards lying anywhere in the polygon, we show that computing an optimal guard set for the vertices of such a polygon is NP-hard. © 2013 Springer-Verlag.

Idioma: Inglês

Tipo (Avaliação Docente): Científica