Guarding polyhedral terrains
We prove that ⌊n/2⌋vertex guards are always sufficient and sometimes necessary to guard the surface of an n-vertex polyhedral terrain. We also show that ⌊(4n - 4)/13⌋ edge guards are sometimes necessary to guard the surface of an n-vertex polyhedral terrain. The upper bound on the number of edge guards is ⌊n/3⌋ (Everett and Rivera-Campo, 1994). Since both upper bounds are based on the four color theorem, no practical polynomial time algorithm achieving these bounds seems to exist, but we present a linear time algorithm for placing ⌊3n/5⌋ vertex guards for covering a polyhedral terrain and a linear time algorithm for placing ⌊2n/5⌋ edge guards.
|Keywords||Art gallery theorems, Matching, Polyhedral terrains|
Bose, P, Shermer, T. (Thomas), Toussaint, G. (Godfried), & Zhu, B. (Binhai). (1997). Guarding polyhedral terrains. Computational Geometry, 7(3), 173–185. doi:10.1016/0925-7721(95)00034-8