I do not know whether it is helpful for you, but there is such a method.
If you set some seam, it may be improved.

Yes I know I can escape concave edges by manualy mark seam/sharp edges, and in this case where I provided example scene as simple is it could possibly be—it looks like an OK solition. But production models are much more difficult than this, and sometimes I have to deal with STL models where it is impossible to select edge loops because it's all triangulated by format standard.

float precision is causing problems here, using double precision for quadric operations makes the example work as expected.

However this is just not going to be well supported (even with doubles, it may be possible to get a more extreme case to fail).

The problem is there are so many faces and they are so small, forming a near flat surface.
Because they are so small, the difference around some parts of the model is detected as zero.

Subdividing a mesh to make a near flat surface then applying decimate, is a rather contrived example. (fine for report of course).

@Mikhail Rachinskiy (alm), Could you show a practical example which causes this problem?

Edge collapsing is likely to cause some artifacts, In the cases you use it, its possible you'd be better off with re-meshing algorithm rather then decimation.
Or make decimation topology aware, to give better results (which is a much bigger change).

While checking on this report exposed some other issues.
rB24e1d7f4f4aba8e94effd6aec4a3d7d8308d4015
rBb5bf5b36f127079f81929ec970ec4d562f92d601

With these changes, the test file looks better then it did before, but the artifacts pointed out are still noticeable.

Subdividing a mesh to make a near flat surface then applying decimate, is a rather contrived example.

You have no idea:
http://www.bulgari.com/en-ch/products.html?product_detail_one=228&root_level=315&sign=18
http://www.bulgari.com/en-ch/products.html?product_detail_one=228&root_level=315&sign=21
http://www.bulgari.com/en-ch/products.html?product_detail_one=228&root_level=315&sign=48
http://www.korloff.fr/en/Jewelry/St-Petersbourg
http://www.korloff.fr/en/Jewelry/Yasmine
http://www.carreraycarrera.com/en/collections-en/baile-de-mariposas-collection
http://www.cartier.com/collections/jewelry/collections/trinity-de-cartier
…you got the point :)

Simple example I've provided actually represents the problem of triangle reduction of jewelry ring quite well.
But here are two production examples:

1. Part of the trinket:
   trinket.blend3 MBDownload
2. Part of the not bulgari earring:
   notbulgari_earring.blend4 MBDownload

I can understand why there are issues with trinket part on the flat surface with little spheres carved out (but if you could fix it by adding another delimiter to the modifier—that would be just wonderful), but on the bottom of that part you can see exactly the problem I illustrated with the example file, the same thing with not bulgari earring part (note: it may take a while to perform reduction in this case).

Thanks for the fixes! I haven't been able to test them yet tho.

Edge collapsing is likely to cause some artifacts, In the cases you use it, its possible you'd be better off with re-meshing algorithm rather then decimation.

Well, if you brought that up yourself :) T39748

Collapse decimation looks really beautiful now.
Big thanks for what you've done, it will spare me (and not only me) if not from all, but at least from part of the issues with decimation.

WOW! This is the result I was looking for!