On computing the convex hull I'm given $n$ points $(p_1, p_2, \ldots, p_n)$, lying on the boundary of a polygon and constituting this polygon (not necessarily convex), whereby those points are given me in clockwise order and I  want to compute the convex hull of this polygon, i.e. determine the set of points $S \subseteq \{p_1, p_2, \ldots, p_n\}$ s.t. the points in $S$ shape the convex hull of the polygon. The tricky part is that my runtime constraint is $O(n)$, which is why I'm very stuck on this task. One should output the points of the convex hull in counterclockwise order.
 A: One algorithm that does the above is Lee's algorithm, explained in this paper
https://link.springer.com/content/pdf/10.1007/BF00993195.pdf
A: Given an unordered set of points, Graham scan yields their convex hull in O(N log N) time complexity.  The limiting factor is the sort phase; everything else is linear in time, as the Wikipedia article explains.
When N is a positive integer with a known maximum (for example, 232-1 when using C uint32_t, or 264-1 when using C uint64_t type), you can use radix sort to do the sort phase in linear time, yielding an implementation of Graham scan with linear time complexity, but with a fixed upper limit for N.
If the points are given in a suitable order, other algorithms can be used to achieve linear time complexity.
Quite a few algorithms assume the points given are the vertices of a polygon in order – meaning that each consecutive pair of points given are connected with an edge in the polygon, with the initial and final points also connected with an edge.
Melkman's Convex Hull Algorithm is probably the best known of these; the Wikipedia Convex hull of a simple polygon article lists a couple more.  These assume that the polygon given is simple (does not intersect itself, and has no holes); some also assume the polygon is not degenerate (a line segment) or that consecutive points (polygon vertices) are not collinear.
I would recommend you examine your data properties, to see how you can get under the O(N log N) time complexity boundary (due to sorting); either by (implicitly) limiting N (so you can use radix sort with linear time complexity), or by leveraging data order (avoiding the need to sort altogether).
Finally, note that time complexity is not a measure of computational efficiency, but of how an algorithm scales as the problem set grows.  In particular, radix sort algorithms tend to be "slow" in practice, with several O(N log N) being "faster" up to a very large N (last time I checked, on the order of millions to hundreds of millions, depending on exact implementation – computer cache architecture details being a deciding factor!).
