Efficient algorithms for computing the maximum distance between two finite planar sets

An 0(n log n) algorithm is presented for computing the maximum euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity can be reduced to 0(n). The algorithm is empirically compared to the brute-force method as well as an alternate 0(n²) algorithm. Both the 0(n log n) and 0(n²) algorithms run in 0(n) expected time for many underlying distributions of the points. An ε{lunate}-approximate algorithm can be obtained that runs in 0(n + 1 ε{lunate}) worst-case time.