# “conservative approximate Set Cover”?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$).

The task is to approximately cover $L$ with translated, rotated and flipped copies of $S$ without pairwise intersections, i.e. find the optimal number of replicas $N^*$ and respective group operations (a finite set) $\mathbf{a}^*$

$\textbf{a}^*, N^* = \mathop{\arg \max}_{\textbf{a}, N} \sum\limits_i^N \mu(s_i)$

s.t. $\bigcap\limits_i^N s_i = \emptyset$,

with $s_i = a_i(S) \in L$ being the application of the $i$th group operation to $S$, and $\mu(s_i) = \mu(S)$ the measure of $S$ e.g.

* * *
*


could approximate $L:=\{(i,j)\,|\,0 \leq i \leq 3,\, 0\leq j \leq 4 \}$ in the above sense as follows:

* . . *
* * * *
* . . *
. * . .
* * * .


or

* * * *
* * * *
* . * *
. * . *
* * * .


etc.

I am thinking that some form of hierarchical rejection sampling should do. However my question is:

Is this a known algorithm, and if so, could someone point me to some references?

(In fact, I am pretty sure this is a special case of some well-known algorithm, I'm just not sure how to represent it. NB: I'm not a CS by education and this is not a homework problem)