Hints for Assignment 4

Define the left boundary of K to be the point of S which has the smallest x value, if there is only one. If there are multiple points of S with the same smallest x value, the left boundary is defined to be the vertical interval that contains them all. The right boundary is defined similarly. Thus, for the points in the file points02, the left boundary consists of the single point (0,4), while the right boundary consists of the vertical interval from (6,4) to (6,5).
Define the upper boundary to be the upper polygonal path along the boundary of K between the left boundary and the right boundary. The lower boundary is defined similarly. For points02, the upper boundary is the path ((0,4),(2,8),(6,5)).
Here is a technique for finding the upper boundary.
  1. Sort the points by their x coordinates and store them in a list called U.
  2. Delete points from U according to the following rules.
    1. Delete duplicate points from U.
    2. If there are two points in U with the same x value, delete the one with the smaller y value.
    3. If there are three consecutive points of U, say P1, P2, and P3, such that P2 is not strictly above the line segment drawn from P1 to P3, delete P2.
  3. If no more points can be deleted from U using the above rules, U is the upper boundary.
The lower boundary is found in a similar way.
Sorting the list can be done in O(n log n) time. The upper boundary can be obtained, by the deletion process, in O(n) time, as can the lower boundary. The area computation then takes O(n) time after that. Thus, the entire algorithm takes O(n log n) time.