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

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?

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