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.