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.