Polyline Averaging I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them.   The input lines do not loop.  
Essentially, I want to do something similar to that of taking multiple GPS routes which are individually subject to noise and producing a single smoothed average of them.
Are there any existing algorithms which can do this?
 A: One of the most attractive distance measures between two curves is the
Fréchet distance, which is the smallest leash length between a dog on one curve and
its owner on the other.
Algorithms for computing it have been studied since the mid-90's, perhaps starting with
this paper:

H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Intl. J. Computational Geometry and Applications, 5:75-91, 1995.

Two curves http://www.win.tue.nl/~wmeulema/images/matching.png
[Image from Wouter Meulemans' web page.]
Once you have committed to this distance measure, it is natural to define a median curve as that which
minimizes the maximum Fréchet distance between it and the curves in your collection.
And indeed this has just been explored in a recent Ms. thesis:

Benjamin Raichel and Sariel Har-Peled. "The Frechet Distance Revisited and Extended." 2012.
  (conference paper link). 

The exact median curve of $k$ $n$-vertex polygonal chains can be computed in $O(n^k)$ time.
But under a natural restriction that the curves are $c$-packed," the exponential time complexity is reduced to $O(n \log n)$ for a $(1+\epsilon)$-approximation.  All of this is detailed in Raichel's thesis.
I doubt there are existing implementations (because this is so new), but examining this
literature should at the least provide you with one natural model of an "average" curve.
