4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ One can ask just for the bounding lines (rather than line segments) and the question is still interesting. $\endgroup$ Jan 20, 2019 at 1:40
  • $\begingroup$ @BrendanMcKay I like the question, but how would we find a bounding lines without knowing at the same time the two points from the set which are on that line? (Here I ignore the case that several boundary points are co-linear.) Granted, given the lines and the points of the boundary it does not seem easy to recover the edges. But could that happen without having that information and then forgetting it? $\endgroup$ Jan 20, 2019 at 7:41
  • $\begingroup$ @AaronMeyerowitz I don't know the answer. It's just that finding the lines seems to be the minimal requirement which has a chance of having the same complexity as finding the hull as an ordered list of vertices. And I suspect it does. $\endgroup$ Jan 20, 2019 at 11:42

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ that is a really surprising result. $\endgroup$ Jan 20, 2019 at 13:48
2
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ I had the same idea but I can't make it work. If you have a set of $n$ arbitrary numbers, it is easy enough to assign each one an index from $\lbrace 1,\ldots,n\rbrace$, and to later retrieve the number with a given index. But how do you retrieve the index for a given number? The standard approaches either use a data structure with logarithmic cost per query (a balanced tree, or sorting), or have constant time only on average (a hash table). $\endgroup$ Jan 20, 2019 at 11:06
  • $\begingroup$ @BrendanMcKay if you have $n$ arbitrary numbers, store them in an array (that gives the index) Then the “edges” we somehow find can be represented in a second array of length $n$ which started empty and now has $j$ in position $i$ if value[i],value[j] is an edge. We are moving pointers rather than rearranging the array. $\endgroup$ Jan 20, 2019 at 12:07
  • $\begingroup$ Aaron, in order to construct the second array you need to locate entries in the first array on the basis of the value they contain. Specifically, given an edge $x,y$, you need to find the positions of $x$ and $y$ in the first array in order to know which value to store in the second array. $\endgroup$ Jan 20, 2019 at 23:19
  • $\begingroup$ I guess it depends on the details of the data structure. If the coordinates of the given points are (the first two fields of) records stored in a fixed array then an edge from from $x$ to $y$ is perhaps not indicated by putting the coordinates of $y$ into the third and fourth fields of the record for $x.$ instead a third field, initially blank, is set to $j$, the index of $y$. Then in one pass one can list the edges in no special order by: If record $i$ has third field no longer blank but now $j$ then list the coordinates at of record $i$ then those of record $j.$ $\endgroup$ Jan 22, 2019 at 6:32
  • $\begingroup$ After that, examine record $i+1$ to see if it has third field blank or not. Instead, one could, after dealing with record $i$, immediately consider record $j$ and in this manner present the edges in order. $\endgroup$ Jan 22, 2019 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.