Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain
Prosenjit K. Bose, David G. Kirkpatrick, Zaiqing Li · 1996
We present efficient polynomial time algorithms that place bn=2c vertex guards which cover the surface of an n-vertex polyhedral terrain, and similarly, bn=3c edge guards which cover the surface of an n-vertex polyhedral terrain. The time complexity of both algorithms, dominated by the cost of finding a maximum matching in a graph, is O(n ).