Exercise 2: (9+6+5) = 20

1. Describe (in natural language) a more efficient algorithm than the

Brute ForceClosest Points(P) to solve the closest-pair problem for n points X1, X2, ...,

Xn on the real line? (Hint: sorting can be done in O(n log n) comparisons)

2. Find the convex hulls of the following sets and identify their extreme points (if they

have any):

a. a line segment

b. a square

c. the boundary of a square

d. a straight line

3. Design a linear-time algorithm to determine two extreme points of the convex hull of a

given set of n> 1 points in the plane.