Face-guarding polyhedra

摘要

We study the Art Gallery Problem for face guards in polyhedral environments. The problem can be informally stated as: how many (not necessarily convex) windows should we place on the external walls of a dark building, in order to completely illuminate its interior? We consider both closed and open face guards (i.e., faces with or without their boundary), and we study several classes of polyhedra, including orthogonal polyhedra, 4-oriented polyhedra, and 2-reflex orthostacks. We give upper and lower bounds on the minimum number of faces required to guard the interior of a given polyhedron in each of these classes, in terms of the total number of its faces, f. In several cases our bounds are tight:「f/6」open face guards for orthogonal polyhedra and 2-reflex orthostacks, and「f/4」open face guards for 4-oriented polyhedra. Additionally, for closed face guards in 2-reflex orthostacks, we give a lower bound of 「(f + 3)/9」 and an upper bound of 「(f + 1)/7」. Then we show that it is NP-hard to approximate the minimum number of (closed or open) face guards within a factor of Ω(logf), even for polyhedra that are orthogonal and simply connected. We also obtain the same hardness results for polyhedral terrains. Along the way we discuss some applications, arguing that face guards are not a reasonable model for guards patrolling on the surface of a polyhedron.