Incorrect Diameter Algorithms for Convex Polygons
Matthew J. Suderman
School of Computer Science
McGill University
January 30, 2001
Introduction
Diameter Algorithm Based on Convex Hull
Diameter of a Convex Polygon
Three Algorithms for Finding the Diameter of a Convex Polygon
Snyder and Tang Algorithm[6]
Dobkin and Snyder Algorithm[3]
Shamos Algorithm[5]
Counterexamples for Two Incorrect Algorithms
Algorithm Counterexample I
Algorithm Counterexample II
What's Wrong with the Algorithms?
Conclusions
Bibliography
Proofs
Proof of Theorem 1.1
The Correct Part of the Dobkin and Snyder Correctness Proof
Proof of Theorem 3.1
Proof of Corollary 3.1a
Glossary
About this document ...
Matthew Suderman
Cmpt 308-507
