1
$\begingroup$

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)

Thank you in advance

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.