Optimal algorithms for computing the minimum distance between two finite planar sets

Godfried T. Toussaint, Binay K. Bhattacharya

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)79-82
Number of pages4
JournalPattern Recognition Letters
Issue number2
StatePublished - Dec 1983


  • 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