Teaching - Convex Hull

Convex Hull

Suggested Reading

de Berg, M., O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry. Springer (2008). Publisher Website, Author Website

convex versus not convex — FIG. 1. Cartoon depiction of a convex hull.

Downloadable Files

Lecture
Computational Geometry: Chapter 01 Introduction
m-file

convex hull rubber band analogy — FIG. 2. Cartoon depiction of a rubber band analogy.

Graham scan example — FIG. 3. Cartoon depiction of a Graham’s scan. (a) The sequence is satisfied with the addition of the red point. (b) The sequence is denied with the addition of the red point. (c) Removing the middle point (orange) from (b), the sequence is again denied, as the orange point and the red point are collinear with the blue point. (d) Removing the middle point from (c), the sequence is confirmed.