ebooks logo journals logo reference works logo abstract databases logo
bullet  SIGN IN Register | Why Register? | Got a Voucher? alerts   marked lists   shopping cart 

informaworld

HOME   |   SEARCH   |   BROWSE
    Issues List       Latest Issue       Forthcoming Articles       Volume 80 Issue 7       Subscribe       Article       References       Related articles      
<< firstfirst   < prevprev   Table of contentstoc   next >next   last >>last
Publisher Logo Publication Cover
Search within this journal

ON THE LOWER BOUND OF EDGE GUARDS OF POLYHEDRAL TERRAINS 

Authors: Branko Kauccaroniccaron a;  Borut Zcaronalik b; Franc Novak c
Affiliations:   a University of Maribor, Faculty of Education, Department of Mathematics, Koroscaronka 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: journal International Journal of Computer Mathematics, Volume 80, Issue 7 July 2003 , pages 811 - 814
Number of References: 5
Formats available: PDF (English)
Article Requests: Order Reprints : Request Permissions
View Article: View Article (PDF) 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)
Bookmark with:
  • CiteULike
  • Del.icio.us
  • BibSonomy
  • Connotea
  • More bookmarks
Privacy Policy | Terms & Conditions | Accessibility | RSS
FAQs in: English . Français . Español . 中文(简体和繁體)
© 2009 Informa plc