Cross-Stitching Using Little Thread



We consider the problem of cross-stitching a predetermined pattern on a piece of fabric. We show that computing stitching sequence that minimizes the amount of thread used when cross-stitching a pattern is NP-hard. However if the region to be stitched is connected, then the optimal solution can be obtained in linear time.

Bibtex Entry