A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets

Godfried T. Toussaint, Jim A. McAlear

Research output: Contribution to journalArticle

Abstract

A simple O(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 reduces to O(n).

Original languageEnglish (US)
Pages (from-to)21-24
Number of pages4
JournalPattern Recognition Letters
Volume1
Issue number1
DOIs
StatePublished - Oct 1982

Keywords

  • Distance between sets
  • algorithms
  • cluster analysis
  • convex hull
  • diameter
  • geometric complexity
  • pattern recognition

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets'. Together they form a unique fingerprint.

  • Cite this