Guarding the Vertices of Thin Orthogonal Polygons is Hard

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

Autores

Ana Paula Tomás (Autor) FCUP

Ata de Conferência Internacional

Título: XV Spanish Meeting on Computational Geometry (EGC 2013)

Páginas: 11-14

http://congreso.us.es/ecgeometry/

Sevilla, Spain, 26 a 28 de Junho de 2013

Classificação Científica

FOS: Ciências exactas e naturais

CORDIS: Ciências Físicas

Projetos Associados

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

Outras Informações

Resumo (PT): 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 the <b>vertices</b> of a thin orthogonal polygon is NP-hard either for guards lying on the boundary, or on vertices or anywhere in the polygon.

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 the <b>vertices</b> of a thin orthogonal polygon is NP-hard either for guards lying on the boundary, or on vertices or anywhere in the polygon.

Idioma: Inglês

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

Notas: http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf