ISSN:
1432-2315
Keywords:
Diameter
;
Expected complexity
;
Monte Carlo simulation
;
Approximate algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n 2) 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01901195
Permalink
