Convex Hull

1. Introduction

The Convex Hull of a set of points P is the smallest convex polygon CH(P) for which each point in P is either on the boundary of CH(P) or in its interior. Imagine that the points are nails on a flat 2D plane and we have a long enough rubber band that can enclose all the nails. If this rubber band is released, it will try to enclose as small an area as possible. That area is the area of the convex hull of these set of points/nails. Finding convex hull of a set of points has natural applications in packing problems.

2. Slide 2


3. Slide 3