# Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$.

My first guess was QuickHull, which has a best case running time of $O(n \log n )$ and a worst case running time time of $O(n^2)$. However, I am a little bit confused about the fact that this convex hull does not have to contain all points. Can I ignore this? I guess yes because I must assume the worst case and this would include all points.

Any ideas or hints?

• Have you seen other Convex Hull algorithms than Quick Hull? When $m = n$ (for example your points are on circle), you cannot ignore it, and your $m * n$ is just $n^2$ so it looks like Quick Hull description. "Chan and Liu" convex hull might interest you. Are you looking for $\Theta(n~log~m)$? – Evil May 21 '16 at 19:51
• Yes I have seen quite a few other algorithms....I am not looking for Θ(n log m), I am looking for something which has either O(mn) or O(n log n) runtime. – 今天春天 May 21 '16 at 20:05
• What does the phrase "the convex hull of a set of $n$ points $P$ which contains $m$ points" mean? – Joseph O'Rourke May 22 '16 at 1:28
• Sorry I'll rewrite this. There are $n$ possible points and the convex hull should contain $m$ of that. – 今天春天 May 22 '16 at 6:34
• Have you checked Wikipedia? en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms – Yuval Filmus May 22 '16 at 14:32

The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other one. This runs in time $O(\min(mn,n\log n))$.
In fact, you can do better – Wikipedia lists several $O(n\log m)$ algorithms, which is strictly better than the guarantee you are looking for.
• Do I have to run the algorithms in parallel or is it ok if I do it sequential? So you think all $O(n log m)$ algorithms are suited for this task? – 今天春天 May 22 '16 at 19:08
• 1) I guess I answered this in the comments above. It is possible. 2) $O(min(mn, nlog n) \Rightarrow f < c * min(mn, nlogn)$..and now? – 今天春天 May 22 '16 at 19:56
• The point is that an $O(n\log m)$ algorithm is also an $O(\min(mn,n\log n))$ algorithm, a fact I'll let you prove yourself. (Similarly, an $O(n)$ algorithm is also an $O(n^2)$ algorithm.) – Yuval Filmus May 22 '16 at 20:01
• In fact you don't need any case analysis. Since $\log m = O(m)$ we get $n\log m = O(nm)$, and since $m \leq n$ we get $n\log m \leq n\log n$. – Yuval Filmus May 22 '16 at 21:45