
> 
> **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](https://en.wikipedia.org/wiki/Kirkpatrick%E2%80%93Seidel_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



Complexity of Determining the Edges of Planar Convex Hulls
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](https://repository.upenn.edu/cgi/viewcontent.cgi?article=1272&context=cis_reports).
> 
> 
> 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](https://arxiv.org/abs/1812.01332) (2018).
> 
> 
> 


