Question

Given a set of n points, find a point (not necessarily one of the inputs) that is inside the convex hull of the n points. Your algorithm should run in o(n) time.

Answer 1

1) Find the bottom-most point by comparing y coordinate of all points. If there are two points with same y value, then the point with smaller x coordinate value is considered. Let the bottom-most point be P0. Put P0 at first position in output hull.

2) Consider the remaining n-1 points and sort them by polor angle in counterclockwise order around points[0]. If polor angle of two points is same, then put the nearest point first.