3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Evil May 21 '16 at 19:51
  • $\begingroup$ 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. $\endgroup$ – 今天春天 May 21 '16 at 20:05
  • $\begingroup$ What does the phrase "the convex hull of a set of $n$ points $P$ which contains $m$ points" mean? $\endgroup$ – Joseph O'Rourke May 22 '16 at 1:28
  • $\begingroup$ Sorry I'll rewrite this. There are $n$ possible points and the convex hull should contain $m$ of that. $\endgroup$ – 今天春天 May 22 '16 at 6:34
  • 1
    $\begingroup$ Have you checked Wikipedia? en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms $\endgroup$ – Yuval Filmus May 22 '16 at 14:32
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 今天春天 May 22 '16 at 19:08
  • $\begingroup$ I believe you can answer both questions yourself. Try to use the definitions of running time and big O. $\endgroup$ – Yuval Filmus May 22 '16 at 19:11
  • $\begingroup$ 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? $\endgroup$ – 今天春天 May 22 '16 at 19:56
  • $\begingroup$ 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.) $\endgroup$ – Yuval Filmus May 22 '16 at 20:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus May 22 '16 at 21:45

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.