Preliminary Definition: A subset S of the plane is called convex if and only if for every pair of points p,q in S, the line segment pq is completely contained in S.Convex Hull Definition #1: The convex hull CH(S) of a set S is the smallest convex set that contains S.
Convex Hull Definition #2: The convex hull CH(S) of a set S is the intersection of all convex sets that contain S.
Convex Hull Definition #3: The convex hull CH(S) of a set S is the unique convex polygon which contains S and all of whose vertices are points from S.
Problem: Given a finite set S of planar points, compute CH(S).
Details:
Input: A finite set of points S={p1,p2,....,pn} given as a list of ordered pairs of Cartesian coordinates:{(x1,y1),(x2,y2),...,(xn,yn)}Output: A listing of the vertices of CH(S) in CW order.
Algorithm Idea #1: Test every point pi in S against every other triple of points in S and accept pi as part of CH(S) only if it falls inside no such triangle. When all points are found, sort in CW order.
Geometric properties
revisited?
Algorithm Idea #2: Test every pair of points pi,pj in S and see if all other points pk lie to the right of pipj. We accept a pair (pi,pj) only if no other point pk is found to the left of pipj .