title: Fast algorithm for calculating union of 'local convex hulls'
body: <p>I have a set of 2D points from which I want to generate a polygon (or collection of polygons) outlining the 'shape' of those points, <em>using the following concept</em>:</p>
  
  <p>For each point in the set, calculate the convex hull of all points within radius R of that point. After doing this for each point, take the union of these convex hulls to produce the final shape.</p>
  
  <p>A brute force approach of actually constructing all these convex hulls is something like O(N^2 + R^2 log R). Is there a known, more efficient algorithm to produce the same result? Or perhaps a different way of expressing the problem?</p>
  
  <p>Note: I am aware of alpha shapes, they are different; I am looking for an algorithm to perform what is described above.</p>
  
  <hr>
  
  <p>The following solution does not work - disproved experimentally in MATLAB.</p>
  
  <p><strike>
  Update: I have a proposed solution.</p>
  
  <p>Proposition: take the Delaunay Triangulation of the set of points, remove all triangles having circumradius greater than R. Then take the union of the remaining triangles.
  </strike></p>