Looking at the other answers I'm not sure anymore. A convex hull means a banana shape would be represented as a semicircle.

You seem to want a tight (not necessarily convex) vector graphic enclosing a sprite.

I think you could achieve this by improving the convex hull (by replacing long edges with concave triangles until all edges are sufficiently "short" or "tight")

Another problem I see are non-connected segments/territories . The shape of the USA would look very different if Alaska and Hawaii were included into just one hull ...

update

Found this http://stackoverflow.com/questions/7408470/given-a-vector-of-points-possibly-out-of-order-find-polygon-not-convex-hull

Pointing to the next problem There is no unique solution for a concave polygon

So starting from a convex hull and improving it till criteria are met is sensible.

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...

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery}

update

added clarification