DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 849

22.22

✓ ✓

What is backtracking? Give an example.

Check

22.23

Point

If you generalize the Eight Queens problem to the n -Queens problem in an n -by- n
chessboard, what will be the complexity of the algorithm?

22.10 Computational Geometry: Finding a Convex Hull
This section presents efficient geometric algorithms for finding a convex hull for a set
of points.

Key
Point

Computational geometry is to study the algorithms for geometrical problems. It has appli-
cations in computer graphics, games, pattern recognition, image processing, robotics, geo-
graphical information systems, and computer-aided design and manufacturing. Section 22.8
presented a geometrical algorithm for finding the closest pair of points. This section intro-
duces geometrical algorithms for finding a convex hull.
Given a set of points, a convex hull is the smallest convex polygon that encloses all these
points, as shown in Figure 22.8a. A polygon is convex if every line connecting two vertices is
inside the polygon. For example, the vertices v0, v1, v2, v3, v4, and v5 in Figure 22.8a form
a convex polygon, but not in Figure 22.8b, because the line that connects v3 and v1 is not
inside the polygon.

convex hull

v3

v3

v2

v4

v4

v2

v1

v1

v5

v5

v0 v0

(a) A convex hull (b) A nonconvex polygon (c) Convex hull animation

F IGURE 22.8

A convex hull is the smallest convex polygon that contains a set of points.

A convex hull has many applications in game programming, pattern recognition, and
image processing. Before we introduce the algorithms, it is helpful to get acquainted with the
concept using an interactive tool from www.cs.armstrong.edu/liang/animation/ConvexHull.html , as
shown in Figure 22.8c. This tool allows you to add and remove points and displays the convex
hull dynamically.
Many algorithms have been developed to find a convex hull. This section introduces two
popular algorithms: the gift-wrapping algorithm and Graham's algorithm.

convex hull animation on the
Companion Website

22.10.1 Gift-Wrapping Algorithm
An intuitive approach, called the gift-wrapping algorithm , works as shown in Listing 22.12:

L ISTING 22.12

Finding a Convex Hull Using Gift-
Wrapping Algorithm
Step 1: Given a list of points S , let the points in S be labeled s 0 , s 1 ,
..., s k . Select the rightmost lowest point S . As shown in Figure 22.9a,
h 0 is such a point. Add h 0 to list H . ( H is initially empty. H will hold
all points in the convex hull after the algorithm is finished.) Let t 0
be h 0 .