patternMinor
Convex hull algorithm in $O(\min(mn, n\log n))$
Viewed 0 times
convexloghullminalgorithm
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#57719, answer score: 4
Revisions (0)
No revisions yet.