On the lower bound of edge guards of polyhedral terrains
B. Kaučič, B. Žalik, F. Novak
International Journal of Computer Mathematics, 2003, 80: 811-814
Guarding polyhedral terrains is a relatively new problem in computational geometry. It is known as NP-hard problem. In 1997, P. Bose, T. Shermer, G. Toussaint and B. Zhu stated the bounds on the number of guards and proposed some algorithms for placing vertex and edge guards. In this contribution, we point to the inconsistency in the proof of the lower bound of the number of edge guards. We show that following the approach of Bose et al. for an n-vertex polyhedral terrain only a weaker lower bound of (2n-4)/7 can be achieved. Hence deriving the proof for the lower bound equal to (4n-4)/13 originally stated by Bose et al. remains an open issue.
BIBTEX copied to Clipboard