Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n2) 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.
- Approximate algorithm
- Expected complexity
- Monte Carlo simulation
ASJC Scopus subject areas
- Computer Vision and Pattern Recognition
- Computer Graphics and Computer-Aided Design