algorithm - Convex Hull in O(n) time -

algorithm - Convex Hull in O(n) time -

show convex hull of n points in plane can computed in o(n) time if each coordinate of each point rational number of form p/q , bounded values p , q.

note : homework problem. can think of using jarvis march somehow avoiding scan of points. maybe can done throwing rays in fixed directions (using rational condition) check next point exists.

don't utilize jarvis march since has time complexity of o(nh). in worst case, h may big n. note h number of points on hull.

instead, should use, example, graham scan time complexity o(nlogn). in graham scan algorithm, time complexity dominated of sorting points. note comparing based sorting algorithms have time complexity of o(nlogn).

in homework problem, can utilize radix sort instead of comparing based sorting algorithms beat lower bound of o(nlogn) since there's assumption coordinates of points bounded. note when inputs sorted bounded radix sort can used, has complexity of o(n).

see here comparisons of various convex hull algorithms.

algorithm computational-geometry convex-hull