### Abstract

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^{2}) algorithm. Both the 0(n log n) and 0(n^{2}) 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.

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

Pages (from-to) | 121-136 |

Number of pages | 16 |

Journal | Journal of Algorithms |

Volume | 4 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1983 |

### ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Efficient algorithms for computing the maximum distance between two finite planar sets'. Together they form a unique fingerprint.

## Cite this

Bhattacharya, B. K., & Toussaint, G. T. (1983). Efficient algorithms for computing the maximum distance between two finite planar sets.

*Journal of Algorithms*,*4*(2), 121-136. https://doi.org/10.1016/0196-6774(83)90040-8