  Biedl et al. introduced the minimum ply cover problem in CG 2021 following
the seminal work of Erlebach and van Leeuwen in SODA 2008. They showed that
determining the minimum ply cover number for a given set of points by a given
set of axis-parallel unit squares is NP-hard, and gave a polynomial time
$2$-approximation algorithm for instances in which the minimum ply cover number
is bounded by a constant. Durocher et al. recently presented a polynomial time
$(8 + \epsilon)$-approximation algorithm for the general case when the minimum
ply cover number is $\omega(1)$, for every fixed $\epsilon > 0$. They divide
the problem into subproblems by using a standard grid decomposition technique.
They have designed an involved dynamic programming scheme to solve the
subproblem where each subproblem is defined by a unit side length square
gridcell. Then they merge the solutions of the subproblems to obtain the final
ply cover. We use a horizontal slab decomposition technique to divide the
problem into subproblems. Our algorithm uses a simple greedy heuristic to
obtain a $(27+\epsilon)$-approximation algorithm for the general problem, for a
small constant $\epsilon>0$. Our algorithm runs considerably faster than the
algorithm of Durocher et al. We also give a fast $2$-approximation algorithm
for the special case where the input squares are intersected by a horizontal
line. The hardness of this special case is still open. Our algorithm is
potentially extendable to minimum ply covering with other geometric objects
such as unit disks, identical rectangles etc.
