Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
By polyline I presume you mean a piecewise linear curve? Or a more general marked curve? And you want a path through what, precisely? –  David Roberts May 9 '12 at 8:46
    
Yes, a piecewise linear curve although not monotonically increasing on either axis. I'm aware that an "average" line is not well defined but I'm looking for a single path which is representative of the input lines. At present I have a scheme in place which finds the start and end points for the "average" line and then iteratively bisects the line and fits the mid point to the input lines. This works well for situations when the lines are straight or 'L' shaped but doesnt work for 'S' type shapes or nything more complex. –  Chris May 9 '12 at 9:10
add comment

1 Answer

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 [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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.