Key points are not available for this paper at this time.
The Orthogonal Polygon Covering with Squares (OPCS) problem takes as input an orthogonal polygon P without holes with n vertices, where vertices have integral coordinates. The aim is to find a minimum number of axis-parallel, possibly overlapping squares which lie completely inside P, such that their union covers the entire region inside P. Aupperle et. al~aupperle1988covering provide an O (N^1. 5) -time algorithm to solve OPCS for orthogonal polygons without holes, where N is the number of integral lattice points lying in the interior or on the boundary of P. Designing algorithms for OPCS with a running time polynomial in n (the number of vertices of P) was discussed as an open question in aupperle1988covering, since N can be exponentially larger than n. In this paper we design a polynomial-time exact algorithm for OPCS with a running time of O (n^14). We also consider the following structural parameterized version of the problem. A knob in an orthogonal polygon is a polygon edge whose both endpoints are convex polygon vertices. Given an input orthogonal polygon with n vertices and k knobs, we design an algorithm for OPCS with running time O (n² + k^14 n). In aupperle1988covering, the Orthogonal Polygon with Holes Covering with Squares (OPCSH) problem is also studied where orthogonal polygon could have holes, and the objective is to find a minimum square covering of the input polygon. This is shown to be NP-complete. We think there is an error in the existing proof in aupperle1988covering, where a reduction from Planar 3-CNF is shown. We fix this error in the proof with an alternate construction of one of the gadgets used in the reduction, hence completing the proof of NP-completeness of OPCSH.
Dhar et al. (Tue,) studied this question.