Find polygon with smallest perimeter that encompasses all points

Given a random set of points in 2D space such as: How would one go about finding the smallest perimeter polygon that encompasses all points and has a point as each one of its vertices? For the above diagram the polygon would be: • Are you looking for a theoretical solution or a practical one that you can apply? – N. Owad Feb 11 '15 at 18:08
• A practical one ideally. – terminex9 Feb 11 '15 at 18:09
• For what it's worth, it looks like your bottom line could just go from the bottom-left point to the bottom-right point and you'd get a smaller perimeter. Isn't this the same as the convex hull of the points? – 211792 Feb 11 '15 at 18:10
• @AustinC is right. If you have a non-convex solution, then replacing a concave part with a direct connection shortens the perimeter. Hence tha optimal solution is th eocnvex hull. – Hagen von Eitzen Feb 11 '15 at 18:13
• Yes, AustinC and Hagen are correct. Here is a good page about it. – N. Owad Feb 11 '15 at 18:16