Guarding thin orthogonal polygons is hard

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

Authors

Tomas, AP (Author) FCUP

Conference proceedings International

Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Pages: 305-316

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

Liverpool, 19 August 2013 through 21 August 2013

Indexing

ISI Web of Knowledge

Scopus - 9 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Associated Projects

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

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific