Guarding the Vertices of Thin Orthogonal Polygons is Hard

• Type: Article in International Conference Proceedings Book
• Date: 2013

Authors

Ana Paula Tomás (Author) FCUP

Conference proceedings International

Title: XV Spanish Meeting on Computational Geometry (EGC 2013)

Pages: 11-14

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

Sevilla, Spain, 26 a 28 de Junho de 2013

Scientific classification

FOS: Natural sciences

CORDIS: Physical sciences

Associated Projects

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

Other information

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.

Language: English

Type (Professor's evaluation): Scientific

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