What is the optimal algorithm for merging an arbitrary number of convex hulls?

Question

Preparata & Shamos in "Convex Hulls: Basic Algorithms" (1985), give a linear algorithm for merging two convex hulls in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices in each input hull. Now, if you had a third convex hull to merge of size $l$, you could do that in $O(x+l)$ time, where $x \le n + m$, which should generalize to finding the merge of an arbitrary number of hulls in $O(N)$ time where $N$ is the total number of vertices in all the hulls to be merged.

However, this suggests an obvious $O(N)$ algorithm for finding the convex hull of an arbitrary set of points: iterate through the vertices once to group them into arbitrary triangles, then merge them all in $O(N)$ time.

But finding the convex hull of an arbitrary point set is supposed to have a lower bound of $O(n\log h)$, and I feel like, if it is correct, this construction is too obvious to have been missed for the last 40-ish years!

So, what have I gotten wrong, and what is the most efficient way to merge convex hulls? Does it make a difference if all members of the initial set of convex hulls are non-overlapping?

Answer 1

the result will not be linear.

Doing the merge between partial result and the next hull will be $O(x_{i-1}+m_i)$ where $x_{i-1}$ is the amount of points in the partial result.

So doing the merge iteratively means you end up with $$O(\sum{(x_{i-1}} + {m_i}))$$ $$O(\sum{x_{i-1}} + \sum{m_i})$$

that first sum of $x_i$ will count the resulting points multiple times. This leads to a super linear algorithm up to quadratic in the worst case

To prove this last bit let's create an input set that is a convex hull. Doing your proposed iteration means that $x_i$ grows linearly and $\sum{x_{i}} = O(n^2)$

Answer 2

What is the most efficient way to merge convex hulls?

It depends and we can't really now before hand. Let me first illustrate why there is no general recipe for this.

If we add two of those convex hulls we get a new convex hull with between $n$ and $2n$ vertices. We can't know the size of this result beforehand.[2]

Even the order in which you combine the convex hulls matters as combining multiple convex hulls with the same number of vetrexes in different number can cause a different number of steps. Imagine two pairs of nested axis aligned squares which are symmetric in one axis.

If you merge the inner and outer square first and then merge the result you end up with (4+4)+(4+4)+(4+4) = 12 steps. If you merge the inner square of one side with the outer of the other side you get (4+4)+(4+4)+(6+6) = 16 steps.

Furthermore there are also procedures which can merge more then two convex hulls at once. https://en.wikipedia.org/wiki/Chan%27s_algorithm s does that in it's second phase. Merging more hulls at once is not necessarily always faster.

Assuming we have $l$ different convex hulls with $n$ vertices each. If we merge from the left as you did, we indeed end up with $O(l^2 n)$ steps. However things look different if we merge in a tree-style way under worst case analysis.

In general i am suspicious that throwing away the existing hulls and starting from scratch is a good idea. There a ways to reuse multiple existing hulls and while merge order can matter using complicated heuristics is likely not worth it. In general a tree style merging procedure of roughly equally sized hulls is a good idea.

But finding the convex hull of an arbitrary point set is supposed to have a lower bound of $O(n \log(h))$, and I feel like, if it is correct, this construction is too obvious to have been missed for the last 40-ish years!

Nothing has been missed and these results aren't suprising. You chose pathologically bad merge order by accident.

Does it make a difference if all members of the initial set of convex hulls are non-overlapping?

Another neat idea to consider are bounding boxes or bounding balls. If you know your points are from certain regions which are easy to check for overlaps you can save some comparisons. If you know two convex hulls are not overlapping you know that there exists a hyperplane of appropriate dimension that will seperate each hull into a part to keep and a part to throw away and the combined hulls will be a concation of two segments to keep. When merging multiple non overlapping convex hulls if a vertex would be thrown away during a pairwise merge of two, then you don't need to consider them any further and adding more non overlapping bounding boxes to merge will only increase the region which is thrown away.

In the end none of this will show up the in the complexity analysis. Complexity analysis does not drive implementation decisions. Benchmarks do. Complexity analysis can predict benchmarks to some extent.

[2] With some advanced math it might be possible to do math for points distributed according to some mathematical probability distribution but those results would only be valid for those distributions on average.