Convex Hull in O(n) time if each coordinate of each point is a rational number

Question

Show that the convex hull of n points in the plane can be computed in O(n) time if each coordinate of each point is a rational number of the form p/q , with bounded values for p and q.

Note: This is a homework problem. I can just think of using Jarvis March by somehow avoiding the scan of all points. Maybe this can be done by throwing rays in fixed directions (using the rational condition) to check where the next point exists.

Answer 1

Don't use Jarvis March since it has time complexity of O(nh). In the worst case, h may be as large as n. Note that h is the number of points on the hull.

Instead, you should use, for example, Graham scan whose time complexity is O(nlogn). In Graham scan algorithm, the time complexity is dominated by that of sorting all the points. Note that comparison based sorting algorithms have a time complexity of O(nlogn).

In your homework problem, you can use radix sort instead of any comparison based sorting algorithms to beat the upper bound of O(nlogn) since there's an assumption that the coordinates of the points are all bounded. Note that when the inputs to be sorted are bounded radix sort can be used, which has a complexity of O(n).

See here for comparisons of various convex hull algorithms.