## 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 language | English (US) |
---|---|

Pages (from-to) | 173-185 |

Number of pages | 13 |

Journal | Computational Geometry: Theory and Applications |

Volume | 7 |

Issue number | 3 |

DOIs | |

State | Published - 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