<p><strong>The problem:</strong></p>

<p>I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times q}$ satisfying</p>

<p>1) $1 \leq p,q \leq m$</p>

<p>2) $A(1,1) = A(p,q) = 1$ and $A(i,j) = 0$ otherwise.</p>

<p>I want to find the smallest $n$ and an $(0,1)$-matrix $B_{n\times n}$ so that $B$ <em>contains</em> every matrix in $\mathcal{M}$. We define that $B$ <em>contains</em> a matrix $A$ if and only if there exists $1 \leq i,j \leq n$ so that $A_{p \times q} = B(\{i,\dots,i+p-1\}, \{j,\dots,j+q-1\})$. Informally speaking, we want the template $B$ contains every patterns in $\mathcal{M}$.</p>

<p>The problem looks like a 2D extension of the shortest superstring problem. However, the patterns are very restricted. </p>

<p><strong>The questions:</strong></p>

<p>1) Is this problem NP-hard or not?</p>

<p>2) Could we come up with an approximation algorithm with performance guarantees?</p>

<p>3) If both of questions one and two are hard to answer, what are good heuristics for designing the template $B$? </p>

<p>4) Suppose $\mathcal{M}$ is a given set of matrices without constraints, can we still solve it with an approximation algorithm?</p>

CC BY-SA 3.0
2013-03-21T14:20:50.000Z
Probably I misunderstand the problem, but I wonder why $n=\max\{\max\{p,q\} \mid A_{p\times q} \in \mathcal{M}\}$ doesn't work?
Yoshio Okamoto
CC BY-SA 3.0
2013-03-22T07:36:02.147Z
@Yoshio Every matrix $A$ in $\mathcal{M}$ needs to be an EXACT submatrix of $B$.
Peng Du
<ds.algorithms><np-hardness><approximation-algorithms><optimization>
Small area containing large amount of patterns
Peng Du
# Small area containing large amount of patterns

(Asked by: username_0 on 2013-03-21)

**The problem:**

I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A\_{p\times q}$ satisfying

1) $1 \leq p,q \leq m$

2) $A(1,1) = A(p,q) = 1$ and $A(i,j) = 0$ otherwise.

I want to find the smallest $n$ and an $(0,1)$-matrix $B\_{n\times n}$ so that $B$ *contains* every matrix in $\mathcal{M}$. We define that $B$ *contains* a matrix $A$ if and only if there exists $1 \leq i,j \leq n$ so that $A\_{p \times q} = B(\{i,\dots,i+p-1\}, \{j,\dots,j+q-1\})$. Informally speaking, we want the template $B$ contains every patterns in $\mathcal{M}$.

The problem looks like a 2D extension of the shortest superstring problem. However, the patterns are very restricted.

**The questions:**

1) Is this problem NP-hard or not?

2) Could we come up with an approximation algorithm with performance guarantees?

3) If both of questions one and two are hard to answer, what are good heuristics for designing the template $B$?

4) Suppose $\mathcal{M}$ is a given set of matrices without constraints, can we still solve it with an approximation algorithm?

**Tags:** ds.algorithms, np-hardness, approximation-algorithms, optimization

> **Comments:**
> **username_1**: Probably I misunderstand the problem, but I wonder why $n=\max\{\max\{p,q\} \mid A_{p\times q} \in \mathcal{M}\}$ doesn't work?  
> **username_0**: @Yoshio Every matrix $A$ in $\mathcal{M}$ needs to be an EXACT submatrix of $B$.  

---

## 0 answers

