### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 379-388 |

Number of pages | 10 |

Journal | The Visual Computer |

Volume | 3 |

Issue number | 6 |

DOIs | |

State | Published - Nov 1988 |

### Keywords

- Approximate algorithm
- Diameter
- Expected complexity
- Monte Carlo simulation

### ASJC Scopus subject areas

- Software
- Computer Vision and Pattern Recognition
- Computer Graphics and Computer-Aided Design

## Fingerprint Dive into the research topics of 'Fast algorithms for computing the diameter of a finite planar set'. Together they form a unique fingerprint.

## Cite this

Bhattacharya, B. K., & Toussaint, G. T. (1988). Fast algorithms for computing the diameter of a finite planar set.

*The Visual Computer*,*3*(6), 379-388. https://doi.org/10.1007/BF01901195