1
$\begingroup$

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels.

enter image description here

At a high level pseudo-code, it is obvious that:

count = 0
while set has points:
    points = find points on convex hull
    set.remove(points) 
    count+=1
return count

But I'm asked to give this in O(n^2) time. Graham scan works in O(n*log(n)) time and gift-wrapping in O(n^2) time. Basically, I'm wondering which algorithm should I use internally to find the points on the convex hull efficiently?

If I use gift-wrapping: I'll get O(n^3) time, and with Graham, I'll get O(log(n)n^2) time.

What would be the best way to design an algorithm that solves the problem in O(n^2)?

Thanks in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

Jarvis' March (Gift Wrapping) Algorithm takes $O(nh)$ time, where $h$ is number of points on convex hull.

Hint:
Suppose algorithm takes $i$ iterations to complete, and $h_k$ be the number of points on the $k$th convex hull $(1 \le k \le i )$. Also, let $n_k$ be the number of points remaining after first $k-1$ iterations. (Note that $n_1 = n, n_{i+1} = 0$).
What is $\sum\limits_{k = 1}^ih_k$?

Explanation:
Let the algorithm takes $cnh$ time for some $c > 0$.
At $k$th iteration, the algorithm will take $cn_kh_k$ time.
The algorithm terminates after $i$ iterations. Therefore, the total time taken for the algorithm is: $$\begin{align}\mathrm{Time} &= \sum\limits_{k = 1}^i c n_k h_k \\&= c\sum\limits_{k = 1}^i n_k h_k \\&\le c\sum\limits_{k = 1}^i n h_k\qquad \text{because }\quad n_k \le n \\&= cn \sum\limits_{k = 1}^i h_k \\&= cn \cdot n \qquad \text{because } \sum\limits_{k = 1}^i h_k \text{is total number of points removed in all iterations, which is n} \\&= cn^2 \\&= O(n^2) \end{align}$$

$\endgroup$
8
  • $\begingroup$ But if n=h, then it will take O(n^2)... right? $\endgroup$
    – user143059
    Sep 28, 2014 at 16:13
  • 1
    $\begingroup$ Then, there will be only one iteration and you're done, right? $\endgroup$
    – taninamdar
    Sep 28, 2014 at 16:13
  • $\begingroup$ Err, the summation should be: i*(n-lost_points)*h; $\endgroup$
    – user143059
    Sep 28, 2014 at 16:25
  • $\begingroup$ No, there is no dependency on $i$. Let the time for GW algorithm be $cnh$ for some $c$. So, total time will be $cnh_1 + cn_1h_2 + \cdots + cn_ih_i \le cn \sum_{k = 1}^i h_i$, because each $n_i \le n$. After the last step, you should use the hint in the answer. $n_k$ is number of points left after first $k-1$ iterations. $\endgroup$
    – taninamdar
    Sep 28, 2014 at 16:25
  • $\begingroup$ Thanks. So I should be able to expand the summation with, upload.wikimedia.org/math/8/c/1/… ? That would give me O(cn*(i(i+1))/2) $\endgroup$
    – user143059
    Sep 28, 2014 at 16:33

You must log in to answer this question.