The convex hull of a set of points is the smallest convex polygon that encloses all points in the set. A polygon is convex if any line segment connecting two points inside the polygon lies completely inside the polygon itself (see Figure 17.3a); otherwise, the polygon is concave (see Figure 17.3b). To picture the convex hull for a set of points, imagine a series of pegs on a board. If we wrap a string tightly around the outermost pegs, the shape of the string is the convex hull.

Figure 17.3. (a) A convex polygon and (b) a concave polygon

One way to construct the convex hull for a set of points
*P* is to use a method called *Jarvis’s
march*. Jarvis’s march constructs a convex hull in two
sections, called the *right chain* and
*left chain*. The right chain consists of all
points in the convex hull from the lowest point (the one with the
smallest *y*-coordinate) to the highest. If two
points are equally low, the lowest point is considered to be the one
that is also the furthest to the left (the one with the smallest
*x*-coordinate). The left chain consists of all
points from the highest point back to the lowest. If two points are
equally high, the highest point is considered to be the one that is
also the furthest to the right.

We begin by finding the lowest point in *P* (as described a moment ago), adding it to the convex hull, and initializing another ...

Start Free Trial

No credit card required