Let's say I have objects for which I want to develop a metric (e.g. for continuous sequences similar to DTW or for categorical sequences like Levensthein). Fulfilling the first three requirments is doable, but now I want to make sure the triangular inequality holds as well (which is not the case for DTW e.g.). Which design patterns / recepiece / methods / tricks exist, to make sure, it does hold? How should I approach the issue (without being a genius or waiting for a lucky epiphany)?
For example such objects might be general graphs or just trees, a regex, a distribution, a tensor, a set, a sequence, a function,...
Since I was asked to just adress one type of object, I would like to adress trees. I could say I use an edit distance: The distance is defined as how mancy changes (delete, insert, switch) I need to make to the nodes of one tree to get the other tree. I start at both nodes and dual-iterate through both trees. Once a subtree is not equal the other one, I have to spend a change to rectify this. (This is a very crude algorithm, but since I want to get to the design principles, I hope it is enough.)
For trees, you might take a look at the paper by Billera, Holmes and Vogtmann entitled "Geometry of the space of phylogenetic trees".