Vi visar att vertex vakta en monoton polygon är NP-hård och konstruera en konstant faktor approximation algoritm för interiör bevakning monoton polygoner. Med hjälp av denna algoritm får vi en approximationsalgoritm för invändig bevakning rektilinjära polygoner som har en approximationsfaktor oberoende av antalet hörn av polygonen. Om storleken på det minsta innerskyddet är OPT för en rektilinjär polygon, producerar vår algoritm ett skydd i storlek O(OPT 2 ).
För punktvakter gav Nilsson REF O(OPT 2 )-tillnärmningsalgoritmer för monotona och enkla rektilinjära polygoner.
Approximate Guarding of Monotone and Rectilinear Polygons
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}