I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan.
- Find a point that is guaranteed to be inside the convex hull, this can be done by finding the line connecting the left most and right most points. And then pick a point between the two end points.
- Use the point in (1) as origin and convert all other points into polar coordinate.
- Sort all other points in counter clockwise motion and iterate (same way one orders angles in radian of the unit circle)
- When the point has y coordinate higher than the origin, then the tangent value between the current point and the last point in the convex hull has to go up compared to the last tangent value. If not we need to wrap the previous points to some earlier point to satisfy this requirement.
- When the point has y-coordinate lower than the origin, then the tangent value has to go down.
The running time is $O(n\log n)$ because that is of sorting and for each point in step 4 and 5, one only needs $O(\log n)$ to search for appropriate previous point.
My question is this seems much simpler than Graham scan. Is there any problem in it (correctness) other than the running time in which iteration in Graham scan is only linear while it is $O(n\log n)$ here