Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 173-185 |
Number of pages | 13 |
Journal | Computational Geometry: Theory and Applications |
Volume | 7 |
Issue number | 3 |
DOIs | |
State | Published - Feb 1997 |
Keywords
- Art gallery theorems
- Matching
- Polyhedral terrains
ASJC Scopus subject areas
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics