algorithm - Greatest linear dimension 2d set of points

Question

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)

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))?

Answer 1

An easy way is to first find the convex hull of the points, which can be done in O(n log n) time in many ways. [I like Graham scan (see animation), but the incremental algorithm is also popular, as are others, although some take more time.]

Then you can find the farthest pair (the diameter) by starting with any two points (say x and y) on the convex hull, moving y clockwise until it is furthest from x, then moving x, moving y again, etc. You can prove that this whole thing takes only O(n) time (amortized). So it's O(n log n)+O(n)=O(n log n) in all, and possibly O(nh) if you use gift-wrapping as your convex hull algorithm instead. This idea is called rotating calipers, as you mentioned.

Here is code by David Eppstein (computational geometry researcher; see also his Python Algorithms and Data Structures for future reference).

All this is not very hard to code (should be a hundred lines at most; is less than 50 in the Python code above), but before you do that -- you should first consider whether you really need it. If, as you say, you have only "thousands of points", then the trivial O(n^2) algorithm (that compares all pairs) will be run in less than a second in any reasonable programming language. Even with a million points it shouldn't take more than an hour. :-)

You should pick the simplest algorithm that works.