Guarding polyhedral terrains

Prosenjit Bose, Thomas Shermer, Godfried Toussaint, Binhai Zhu

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)173-185
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume7
Issue number3
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Guarding polyhedral terrains'. Together they form a unique fingerprint.

  • Cite this