Onion-peeling in O(n^2) time

Question

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.

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.

Answer 1

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}$$