Premium
Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
Author(s) -
Schuchardt Dietmar,
Hecker HansDietrich
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410212
Subject(s) - combinatorics , mathematics , vertex (graph theory) , simple (philosophy) , point (geometry) , geometry , graph , philosophy , epistemology
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.