Decimation preserving seams


Is there some way to decimate a mesh which does not create faces that crosses seams?

I have tried the Decimate / Un-subdivide modifier, which gives a reasonable mesh except that faces can cross seams. The first picture shows the original and subdivided meshes

The seam is in the middle of decimated faces. The original UVs are located in two separated regions, but the decimated faces are streched out,

and the render becomes ugly:

Is there some way to avoid this problem, apart from writing a better decimation algorithm myself?

If there are no options in the modifier settings then.

Separate objects int separate parts then decimate and rejoin
Decimate, unwrap the lower poly result then bake the texture from the original model/uvs to the new low poly model/uvs

Thank you for your quick reply.

The second option would work for a given mesh. Alas, I am a scripter rather than a modeler, and am really looking for a general solution that works for all meshes with minimal human intervention. As for the first suggestion, I have tried it and it does not really work. I created a new mesh where each vertex has a unique UV - in other words, any vertex with multiple UVs correspond to several vertices in the new mesh. Decimating the new mesh does make the thigh look better:

You can see a small glitch in the render but it is hardly noticeable. However, there are other regions with bigger problems; in particular, this approach gives a hole in the shoulder:

So I guess that I am really asking for two things:

  1. Decimation preserving seams.
  2. Continuity across seems, so one can use Remove Doubles on the decimated verts and get a seamless mesh.