A Counterexample to a Diameter Algorithm for Convex Polygons

Binay K. Bhattacharya, Godfried T. Toussaint

Research output: Contribution to journalArticle

Abstract

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in 0(n) time.

Original languageEnglish (US)
Pages (from-to)306-309
Number of pages4
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
VolumePAMI-4
Issue number3
DOIs
StatePublished - May 1982

Keywords

  • Algorithm
  • artificial intelligence
  • computational complexity
  • computational geometry
  • convex hull
  • convex polygon
  • image processing
  • pattern recognition
  • region growing
  • scene analysis
  • simple polygon

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Counterexample to a Diameter Algorithm for Convex Polygons'. Together they form a unique fingerprint.

  • Cite this