1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That makes sense! Thanks. So, for 3+ inputs, is it best to just go with a standard algorithm for arbitrary points, or is there some more efficient approach available? $\endgroup$ Aug 19 at 16:23
  • $\begingroup$ @LoganR.Kearsley that depends on the constant factors involved. Which depend on the platform you are running it on and the exact implementation details. $\endgroup$ Aug 21 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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