Incorrect Diameter Algorithms for Convex Polygons (original) (raw)

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