### Abstract

It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced O(n).

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

Pages (from-to) | 79-82 |

Number of pages | 4 |

Journal | Pattern Recognition Letters |

Volume | 2 |

Issue number | 2 |

DOIs | |

State | Published - Dec 1983 |

### Keywords

- Minimum distance between sets
- algorithms
- cluster analysis
- coloring problems
- complexity
- computational geometry
- convex polygons
- pattern recognition

### ASJC Scopus subject areas

- Software
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence

## Cite this

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

*Pattern Recognition Letters*,*2*(2), 79-82. https://doi.org/10.1016/0167-8655(83)90041-7