Fast algorithms for computing the diameter of a finite planar set

Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n ²) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.Research of the first author was supported by grant NSERC A 2422. Research of the second author was supported by grants NSERC A 9293, FCAC EQ-1678 and a Killam Senior Research Fellowship awarded by the Canada Council