A Counterexample to a Diameter Algorithm for Convex Polygons

Binay K. Bhattacharya; Godfried T. Toussaint

doi:10.1109/TPAMI.1982.4767248

A Counterexample to a Diameter Algorithm for Convex Polygons

Binay K. Bhattacharya, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	306-309
Number of pages	4
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	PAMI-4
Issue number	3
DOIs	https://doi.org/10.1109/TPAMI.1982.4767248
State	Published - 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

Access to Document

10.1109/TPAMI.1982.4767248

Cite this

@article{c5ade0de6cde4a869963877f3d56ff84,

title = "A Counterexample to a Diameter Algorithm for Convex Polygons",

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.",

keywords = "Algorithm, artificial intelligence, computational complexity, computational geometry, convex hull, convex polygon, image processing, pattern recognition, region growing, scene analysis, simple polygon",

author = "Bhattacharya, {Binay K.} and Toussaint, {Godfried T.}",

year = "1982",

month = may,

doi = "10.1109/TPAMI.1982.4767248",

language = "English (US)",

volume = "PAMI-4",

pages = "306--309",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - A Counterexample to a Diameter Algorithm for Convex Polygons

AU - Bhattacharya, Binay K.

AU - Toussaint, Godfried T.

PY - 1982/5

Y1 - 1982/5

N2 - 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.

AB - 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.

KW - Algorithm

KW - artificial intelligence

KW - computational complexity

KW - computational geometry

KW - convex hull

KW - convex polygon

KW - image processing

KW - pattern recognition

KW - region growing

KW - scene analysis

KW - simple polygon

UR - http://www.scopus.com/inward/record.url?scp=0020128733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020128733&partnerID=8YFLogxK

U2 - 10.1109/TPAMI.1982.4767248

DO - 10.1109/TPAMI.1982.4767248

M3 - Article

AN - SCOPUS:0020128733

SN - 0162-8828

VL - PAMI-4

SP - 306

EP - 309

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 3

ER -

A Counterexample to a Diameter Algorithm for Convex Polygons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this