Covering a rectilinear polygon with squares Polygon covering

for polygons may contain holes, finding minimum such covering np-hard. sharp difference between hole-free , general polygons can intuitively explained based on following analogy between maximal squares in rectilinear polygon , nodes in undirected graph:

some maximal squares have continuous intersection boundary of polygon; when removed, remaining polygon remains connected. such squares called continuators , analogous leaf nodes – nodes single edge – can removed without disconnecting graph.
other maximal squares separators : when removed, polygon splits 2 disconnected polygons. analogous nodes 2 or more edges that, when removed, leave disconnected remainder.

in hole-free rectilinear polygon, maximal squares either continuators or separators; thus, such polygon analogous tree graph. general polygon analogous general graph. vertex cover problem polynomial tree graphs np-hard general graphs, square covering problem linear hole-free polygons np-hard general polygons.

it possible use linear algorithm 2-approximation – i.e., covering @ 2⋅opt squares, opt number of squares in minimum covering:

for each hole, find square s connecting hole external boundary.
cut s polygon, glue 2 overlapping copies of s (see figure). resulting polygon not planar, still 2-dimensional, , has no holes.
now use original algorithm find minimum covering.

the number of squares in resulting covering @ opt+holes, holes number of holes. possible prove opt≥holes. hence number of squares in covering @ 2⋅opt.