Complexity of Determining the Edges of Planar Convex Hulls

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.

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).