Definition:
The Convex hull of a set of points is the smallest convex set which contains them.
Question:
Assume that $n$ points like $P=\{p_0,p_1,p_2,...,p_{n-1}\}$ are given and all we know is that they belong to the boundary of $CH(P)$. How can we compute $CH(P)$ in $O(n)$ time?
My try:
I know that there is an algorithm for computing the convex hull of a set of points in $O(n)$ time. But that's a more general case. I wonder how we can use the property that all of the points are on the boundary of the convex hull to build the algorithm. As far as I know, including every kind of sorting would take a time of $O(nlogn)$, since sorting cannot be done in less than that. So, we should somehow get rid of sorting. Another related interesting question would be that if someone gives me some edges on the convex position, how can I build the convex hull out of that?
Note: All of the points are in 2D space. The output should be something like the clockwise order of points which make the convex hull.
With the current phrasing, what you ask for can only be done if there exists a sorting algorithm for real numbers that runs in linear time.
Given $n$ real numbers $t_1, \ldots, t_n$, shift and rescale them to fit in the interval $[0, \pi]$. This gives you real numbers $\theta_1,\ldots, \theta_n$ whose order match the original $t_i$'s. Consider the 2D point $p_i$ with coordinates $(\cos\theta_i, \sin\theta_i)$. Every $p_i$ belongs to the boundary of their convex hull.
If you find a counter clock wise ordering of the points $p_i$'s, you have effectively sorted the original numbers $t_i$'s. Since the transformation from number to point takes linear time, the method you're asking for would allow sorting in linear time.
Now as far as I know, the $O(n\log n)$ bound for sorting algorithms only applies to comparison-based sorts. A common example of sort algorithm that isn't compatison-based would be the radix sort for integers, but that one relies on specific properties of integers.
Maybe someone somewhere will one day come up with an actual solution to your question, but you're unlikely to get one anytime soon.