title: Finding smallest polygon covering a set of points in a grid
body: <p>Firstly, I'm not asking for code, I just want clarification about my approach.</p>
  
  <p>Secondly, if this isn't totally SO related, I will move the question to the most relevant Stack Exchange site. I'm pretty sure this is a graph theory related problem.</p>
  
  <p>So I have an infinitely large grid with a defined point (0,0)</p>
  
  <p>Each intersection between horizontal/vertical lines in the grid defines another point (given by the number of lines from the origin).</p>
  
  <p>Given a set of points <code>(x,y)</code> where each <code>x,y</code> is an Integer: return the perimeter of the smallest polygon surrounding the points. </p>
  
  <p>Constraints:</p>
  
  <ul>
  <li>The number of points is less than 100,000</li>
  <li>The points cannot lie on the perimeter of the polygon.</li>
  <li>The sides of the polygon can only correspond to vertical/horizontal lines in the grid, or a diagonal line in a single square.</li>
  </ul>
  
  <p>My guess that the is a Graph Theory related problem. Just like the Travelling Salesman, I first need to find the shortest path between all points using an algorithm which gives an optimal solution. Then I need to perform the same algorithm between each point to find the optimal path along the grid between the points.</p>
  
  <p>I have written an algorithm for the Travelling Salesman given 80 towns.</p>
  
  <p>In this question there can be 100,000 points. So that makes me wonder if a possible algorithm even exists to solve such a huge number of Nodes.</p>
  
  <p>Is there another approach. Am I thinking about this the wrong way?</p>
  
  <p>Thanks for any help!</p>