Complexity of Determining the Edges of Planar Convex Hulls 
Question:
can the set of edges that resemble the convex hull ($CH$ for short) of $n$ points in the euclidean plane be determined in $O(n)$ time?

I know that the time complexity of determining the $CH$ of $n$ points is $O(n\log h)$ where $h$ is the number of points constituting to the $CH$ and is achieved by the Kirkpatrick-Seidel algorithm, but that includes reporting the points of $CH$ in sorted order.
So, can the $\log h$ factor be saved if the edges vertices of the $CH$ can be reported in random order?

Edit:
incidently I realized that the set of edges apparently can't be reported in $O(h)$ when I turned on my computer and then saw the Aaron's comment about the pertinent related question.
The argument against the possibility of reporting the edges in $O(h)$ is simply that the *set of edges contains enough information to be able to also sort * them in $O(h)$ time via the following algorithm:

*

*assume that the $n$ vertices are stored in an array V and labeled with their index in that array

*determine the edges of the $CH$ in random order in $O(h)$ and store them in an array H

*label the edges in H with their index in that array

*create an P that contains pairs of indices of edges in H and initialize all entries with the pair (-1,-1)

*iterate over H and store the edge index in P in the positions of their adjacent vertices, overwriting one of the pair values that equal -1

*P now resembles a doubly linked list from which the sorted order of the edges of $CH$ could be reconstructed in $O(h)$ time

as the possibility of reporting the edges in sorted order in $O(n)$ time clearly contradicts the proven sharp lower bound for the complexity of sorting there is no advantage in reporting the edges of $CH$ in random (or rather: unspecified) order.
However with reporting the vertices of $CH$ in random order the situation is fundamentally different as there is no neighborhood relation that could be exploited to reconstruct the edges of $CH$ in $O(n)$ time
 A: I think not because it wouldn't be hard to go from the edges, given as pairs of points, to the ordered list of edges.
With complexity $n$ we can give each point an index in $\{1,2,\cdots,n\}$ so that we can look up in one step the index from the point or the point from the index. Then given the unordered set of edges, supposing for now that each edge is reported in clockwise order, we can use $2n$ look ups to get an ordered list of edges. If the edges are reported as unordered pairs we can take an internal point (the average of some three points say) and use it to orient all the edges with complexity $O(n).$.
Here is a pertinent related question: 
Given numbers $x_1 \lt x_2 \lt \cdots \lt x_n,$ but in a random order, we know that  $n \log n$ is the complexity to sort them. What is the complexity to return , in no special order, the set of $n-1$  ordered pairs $(x_i,x_{i+1})?$ The same indexing idea as above would seem to allow one to turn that into the sorted list in time $O(n)$ . The connection is that for the $n$ points $(x_i,x_i^2)$, finding the edges of the convex hull is the same as finding those ordered pairs.   
LATER There seems a definitive answer. Here is a toy example to show what I was trying to say: Suppose that the input is $7$ points of which $4$ turn out to be on the boundary of the CH. The input might be a seven element array stored in memory addresses$100,200,\cdots 700.$ Each term is a three field record with $x$ coordinate, $y$ coordinate and third field (the only one that changes) initially NULL.
$\begin{array}{cccc}
100 & 7 & 1 & - \\
200 & 10 & 0 & - \\
300 & 0 & 0 & - \\
400 & 3 & 4 & - \\
500 & 0 & 10 & - \\
600 & 10 & 10 & - \\
700 & 5 & 6 & - \\
\end{array} $
Somehow we end up knowing the edges of the convex hull. I'm thinking that at this stage the array is
$\begin{array}{cccc}
100 & 7 & 1 & - \\
200 & 10 & 0 & 600 \\
300 & 0 & 0 & 200 \\
400 & 3 & 4 & - \\
500 & 0 & 10 & 300 \\
600 & 10 & 10 & 500 \\
700 & 5 & 6 & - \\
\end{array} $
I agree that we might then do one sequential pass through the array and return


*

*$(10,0),(10,10)$

*$(0,0),(10,0)$

*$(0,10),(0,0)$

*$(10,10),(0,10)$
I also agree that given just that list of edges, sorting would be as hard as sorting is. But that is because we threw away information. 
With that data structure there is no issue of finding the address from the coordinates. We know the coordinates because we have the appropriate memory address (i.e. the index.)  So we can as easily (or more easily) visit the memory locations in order $100 \rightarrow 200 \rightarrow 600 \rightarrow 500 \rightarrow 200$ then STOP and return the ordered list of edges.
A: It's been known for some time that the unordered convex hull problem—"just identifying the vertices on the planar convex hull, takes $\Omega(n \log n)$ time":

Ramaswami, Suneeta. "Convex hulls: Complexity and applications (a survey)." Technical Reports (CIS) (1993): 264. PDF download.
Haverkort, Herman. "Finding the vertices of the convex hull, even unordered, takes $\Omega(n \log n)$ time--a proof by reduction from $\epsilon$-closeness." arXiv preprint arXiv:1812.01332 (2018).

