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