Guarding the vertices of thin orthogonal polygons is NP-hard

Description

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.

Abstract

Fondo Europeo de Desarrollo Regional

Abstract

Fundação para a Ciência e a Tecnologia

Additional details