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