<p>Given an ordered set of 2D pixel locations (adjacent or adjacent-diagonal) that form a complete path with no repeats, how do I determine the Greatest Linear Dimension of the polygon whose perimeter is that set of pixels? (where the GLD is the greatest linear distance of any pair of points in the set)</p>

<p>For my purposes, the obvious O(n^2) solution is probably not fast enough for figures of thousands of points. Are there good heuristics or lookup methods that bring the time complexity nearer to O(n) or O(log(n))?</p>

On this page:
http://en.wikipedia.org/wiki/Rotating_calipers
http://cgm.cs.mcgill.ca/~orm/diam.html
it shows that you can determine the maximum diameter of a convex polygon in O(n). I just need to turn my point set into a convex polygon first (probably using Graham scan).
http://en.wikipedia.org/wiki/Convex_hull_algorithms
Here is some C# code I came across for computing the convex hull:
http://www.itu.dk/~sestoft/gcsharp/index.html#hull