Convex hull algorithm in $O(\min(mn, n\log n))$
-
03-11-2019 - |
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange