ON THE LOWER BOUND OF EDGE GUARDS OF POLYHEDRAL TERRAINS
Authors:
Branko Kau
i
a;
Borut
alik b;
Franc Novak c
i
a;
Borut
alik b;
Franc Novak c
| Affiliations: | a University of Maribor, Faculty of Education, Department of Mathematics, Koro ka cesta 160, SI-000 Maribor, Slovenia. |
| b University of Maribor, Faculty of Electrical Engineering and Computer Science, Smetanova 17, SI-2000 Maribor, Slovenia. | |
| c Jozef Stefan Institute, Jamova 39, SI-1000 Ljubljana, Slovenia. |
DOI:
10.1080/0020716031000087131
Publication Frequency:
12 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
80,
Issue
7
July
2003
, pages 811
- 814
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 5
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
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.
|
| Keywords: Terrain Guarding; Polyhedral Terrain; Computational Geometry; Graph Theory |
| view references (5) |

Download Citation

ka cesta 160, SI-000 Maribor, Slovenia.
CiteULike
Del.icio.us
BibSonomy
Connotea