Cross-Stitching Using Little Thread. Therese Biedl, Joseph D. Horton, A. López-Ortiz. Proceedings of 16^th Canadian Conference on Computational Geometry, 2005. [Postscript file]

Abstract.
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.