I just saw I was a bit short on the subject with my last post.

As it contained a link to the relevant paper “*Optimal decomposition of polygonal models into triangle strips*” (Regina Estkowski, Joseph S. B. Mitchell, Xinyu Xiang. Proceedings of Symposium on Computational Geometry 2002) it still seems to be awaiting moderator approval.

In the meantime I will try to clarify things.

**Don’t get things wrong:** Nobody claims dissecting a mesh into an **arbitrary** dissection of triangle strips is NP-complete.

Obviously calculating an arbitrary dissection is quite easy to do. Even a list containing every single triangle of a mesh with *n* triangles is a dissection into *n* triangle strips of length 1.

It is the problem of computing an **optimal** dissection into triangle strips that is NP-comlete.

Optimal in the sense, that it is made of a minimal number of triangle strips.

Given the fact that the **k-STRIPABILITY** problem is NP-complete, it is quite easy to see the problem of computing an optimal dissection into triangle strips is NP-complete by reduction:

If I were able to solve the optimal triangle strip dissection problem in polynomial time, I could solve the k-STRIPABILITY in polynomial time as well by just comparing the number of triangle strips in the optimal dissection to k.