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

Question

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?

• Evil: 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)$?
• 今天春天: 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.
• Joseph O'Rourke: What does the phrase "the convex hull of a set of $n$ points $P$ which contains $m$ points" mean?
• 今天春天: Sorry I'll rewrite this. There are $n$ possible points and the convex hull should contain $m$ of that.
• Yuval Filmus: Have you checked Wikipedia? en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms

Answer 1

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?
• Yuval Filmus: I believe you can answer both questions yourself. Try to use the definitions of running time and big O.
• 今天春天: 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?
• Yuval Filmus: 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: 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$.