Title :
A Counterexample to a Diameter Algorithm for Convex Polygons
Author :
Bhattacharya, Binay K. ; Toussaint, Godfried T.
Author_Institution :
School of Computer Science, McGill University, Montreal, P.Q., Canada.
fDate :
5/1/1982 12:00:00 AM
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 O(n) time.
Keywords :
Artificial intelligence; Computational complexity; Computational geometry; Computer science; Euclidean distance; Image analysis; Image processing; Moon; Pattern recognition; Performance evaluation; Algorithm; artificial intelligence; computational complexity; computational geometry; convex hull; convex polygon; image processing; pattern recognition; region growing; scene analysis; simple polygon;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
DOI :
10.1109/TPAMI.1982.4767248
