✦ LIBER ✦
Two NP-Hard Art-Gallery Problems for Ortho-Polygons
✍ Scribed by Dietmar Schuchardt; Hans-Dietrich Hecker
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 292 KB
- Volume
- 41
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
D. T. Lee and A. K. Lin [2] proved that VERTEX‐GUARDING and POINT‐GUARDING are NP‐hard for simple polygons. We prove that those problems are NP‐hard for ortho‐polygons, too.