George T. Heineman - Algorithms in a Nutshell: A Desktop Quick Reference

Beijing Cambridge Farnham Kln Sebastopol Tokyo

The first step to design an algorithm is to understand the problem you want to solve. Lets start with a sample problem from the field of computational geometry. Given a set of points, P , in a two-dimensional plane, such as shown in , picture a rubber band that has been stretched around the points and released. The resulting shape is known as the convex hull , that is, the smallest convex shape that fully encloses all points in P .

Figure 1-1. Sample set of points in plane

Given a convex hull for P , any line segment drawn between any two points in P lies totally within the hull. Lets assume that we order the points in the hull in clockwise fashion. Thus, the hull is formed by a clockwise ordering of h points L0 , L1 , Lh-1 as shown in . Each sequence of three hull points Li , Li+1 , Li+2 creates a right turn.

Figure 1-2. Computed convex hull for points

With just this information, you can probably draw the convex hull for any set of points, but could you come up with an algorithm , that is, a step by step sequence of instructions, that will efficiently compute the convex hull for any set of points?

What we find interesting about the convex hull problem is that it doesnt seem to be easily classified into existing algorithmic domains. There doesnt seem to be any sorting, although the points are ordered in clockwise fashion around the hull. Similarly, there is no obvious search being performed, although you can identify a line segment on the hull because the remaining n-2 points are to the right of that line segment in the plane.

Naive Solution

Clearly a convex hull exists for any collection of 3 or more points. But how do you construct one? Consider the following idea. Select any three points from the original collection and form a triangle. If any of the remaining n-3 points are contained within this triangle, then they cannot be part of the convex hull. Well describe the general process in using pseudocode and you will find similar descriptions for each of the algorithms in the book.

Slow Hull Summary

Best,Average,Worst: O( n4 )

slowHull(P)foreachp0inPdoforeachp1in{P-p0}doforeachp2in{P-p0-p1}doforeachp3in{P-p0-p1-p2}doifp3iscontainedwithinTriangle(p0,p1,p2)thenmarkp3asinternalcreatearrayAwithallnon-internalpointsinPdetermineleft-mostpointleftinAsortAbyangleformedwithverticallinethroughleftreturnA

Points not marked as internal are on convex hull

These angles (in degrees) range from 0 to 180.

In the next chapter we will explain the mathematical analysis that explains why this approach is considered to be inefficient. This pseudo-code summary explains the steps that will produce the correct answer for each input set (in particular, it created the convex hull in ). But is this the best we can do?

Intelligent Approaches

The numerous algorithms in this book are the results of striving for more efficient solutions to existing code. We identify common themes in this book to help you solve your problems. There many different ways to compute a convex hull. In sketching these approaches, we give you a sample of the material in the chapters that follow.

Greedy

Heres a way to construct the convex hull one point at a time:

1. First locate and remove low , the lowest point in P .
2. Sort the remaining n-1 points in descending order by the angle formed in relation to a vertical line through low . These angles range from 90 degrees for points to the left of the line down to -90 degrees for points to the right. pn-1 is the right-most point and p0 is the left-most point. shows the vertical line as a thick blue line, and the angles to it as light gray lines.
3. Start with a partial convex hull formed from these three points in the order { pn-1 , low , p0 }. Try to extend the hull by considering, in order, each of the points p1 to pn-1 . If the last three points of the partial hull ever turn left, the hull contains an incorrect point that must be removed.
4. Once all points are considered, the partial hull completes.

Figure 1-3. Hull formed using greedy approach

Divide and Conquer

We can divide the problem in half if we first sort all points,