Finding Shortest Path Around

Let S be a set of points in a 2-dimensional plane. The convex hull of set S is the smallest convex set containing S. (Please find more about the convex hull problem, especially the definition of extreme point, on pages 109-113 in the textbook.) It is assumed that not all the points in S are on a straight line.

The points in the convex hull can be viewed as fence posts that support a fence surrounding all the points in S. Let s1 and s2 be two points in the hull. A path from s1 to s2 is a sequence

of points in the hull. By viewing points in the hull as fence posts, we may consider a path as a sequence of posts holding a fence segment. The problem of finding shortest path around is to find the shortest path from si to s2 that cannot cross inside the fenced area, but it goes along the fence. From s1 to s2, there are two paths along the fence, going in the two directions. The problem is to find the shorter one.

2.1 Design a brute force algorithm to solve the shortest path around problem and analyze its efficiency.

2.2 Design a recursive divide-and-conquer algorithm of O(n log n) to solve the shortest path around problem, set up a recurrence to analyze the number of repetitions of the basic operation to compute the hull (for the best case), and determine the efficiency class. Use the Master Theorem to verify the efficiency class that you determine.

2.3 Implement the two algorithms and test them using data A2-Q2.tat. The file contains 30,000 points (pairs of x-y coordinates). Your programs will be graded by using this data file and two points s1 and s2 that are in the hull of the points in the file. Your programs are required to display the number of points on the path, the length of the path, and x-y coordinates of the points (in the order from 81 to 82 inclusive). Your programs are also required to display execution time for hull computing. Compare the two algorithms in execution time and theoretical analysis.

Also, for grading your programs, we request that, when a program identify a hull point, it displays the x-y coordinates.

You can hard-code the name of the data file in your programs. The file (data_A2_Q2.txt) will be used to grade your programs. Your program should prompt to enter s1 and s2.