One more idea

> could achieve this by improving the convex hull

take this "banana", the asterisks * are corners of the convex hull but the dots are not approached.

  

* a

     *
  .  .
     .  *
  .
     .  *
   . 
    . *
  
* b
[download]

Now starting from the edge a-b you could construct a "convex" streak from a to b which keeps all other points "outside", just using the same algorithm like before and inverting the orientation.

Saying so I'm pretty sure there are already ready to use algorithms which do this in a time efficient way...