How to find all equals paths in degenerate tree from specific start vertex?

If I have a set of points defining a particular path, and I have a set of such paths such that these paths deviate from each other only slightly then how do I find the mean path?

• Something like this - Sorry about the bad paint drawing. So I have the above paths. They are relatively close to each other or you can say follow the same pattern. How do I find the mean path?

• Answer:

  Let's say you have four paths, p, q, r and s. If the paths are "time-stamped" (parametrized in time), you can simply take the average point at each time, i.e. (p(t)+q(t)+r(t)+s(t))/4 If you don't have exact timestamps: this means that you don't know which points from p, q, r and s are to be averaged together. Then you need to "align" the paths in time. Maybe the most effective tool to do this is to use http://en.wikipedia.org/wiki/Dynamic_time_warping, which finds the "best" alignment between two sequences. You can use DTW, with using Euclidean distance as cost, to find the alignment between a pair of sequences, then take the averages. One remaining problem is that DTW only finds a matching between a pair of sequences. If you have multiple sequences, you can proceed in a "tournament-like" manner (match p and q to produce the average pq, match r and s to produce the average rs, match pq and rs to produce the final answer), or there are other variants. The wikipedia page on DTW contains some information and links for them.