×

Covering orthogonal polygons by horizontal guards. (English) Zbl 0864.68110

Summary: Covering a simple polygon by the minimum number of point guards under standard visibility is known to be NP-hard. This problem is still open when the polygon is restricted to be orthogonal. We present an \(O(n)\) time algorithm to cover a simple monotone orthogonal polygon by the minimum number of horizontal guards under orthogonal visibility. We then extend the method and develop an \(O(n\log\log n)\) time algorithm to minimally cover an orthogonal polygon (not necessarily monotone) by horizontal quards.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite