This is a tougher problem than I originally thought.. However I dont think that the polygon that I drew could exist in your instance because you're doing a convex hull, which by definition doesnt allow these types of jagged edges, for example, this polygon would have a line going across the crests of the spikes rather than a line going down into it.
You are wrong, as you said earlier, your first idea with the planes would have worked with a convex hull. But the polygon you drew is actually possible, this is why it is a tough problem.
But the Graham Scan generates a convex hull, so unless you aren't using the Graham Scan, it should work.