title: How to select points at a regular density
body: <p>how do I select a subset of points at a regular density? More formally,</p>
  
  <p>Given</p>
  
  <ol>
  <li>a set <strong>A</strong> of irregularly spaced points,</li>
  <li>a metric of distance <code>dist</code> (e.g., Euclidean distance),</li>
  <li>and a target density <strong>d</strong>,</li>
  </ol>
  
  <p>how can I select a smallest subset <strong>B</strong> that satisfies below?</p>
  
  <ul>
  <li>for every point <strong>x</strong> in <strong>A</strong>,</li>
  <li>there exists a point <strong>y</strong> in <strong>B</strong></li>
  <li>which satisfies <code>dist(x,y) &lt;= d</code></li>
  </ul>
  
  <p>My current best shot is to</p>
  
  <ul>
  <li>start with <strong>A</strong> itself</li>
  <li>pick out the closest (or just particularly close) couple of points</li>
  <li>randomly exclude one of them</li>
  <li>repeat as long as the condition holds</li>
  </ul>
  
  <p>and repeat the whole procedure for best luck. But are there better ways?</p>
  
  <p>I'm trying to do this with 280,000 18-D points, but my question is in general strategy. So I also wish to know how to do it with 2-D points. And I don't really need a guarantee of a smallest subset. Any useful method is welcome. Thank you.</p>
  
  <hr>
  
  <h1>bottom-up method</h1>
  
  <ul>
  <li>select a random point</li>
  <li>select among unselected <code>y</code> for which <code>min(d(x,y) for x in selected)</code> is largest</li>
  <li>keep going!</li>
  </ul>
  
  <p>I'll call it bottom-up and the one I originally posted top-down. This is much faster in the beginning, so for sparse sampling this should be better?</p>
  
  <h1>performance measure</h1>
  
  <p>If guarantee of optimality is not required, I think these two indicators could be useful:</p>
  
  <ul>
  <li>radius of coverage: <code>max {y in unselected} min(d(x,y) for x in selected)</code></li>
  <li>radius of economy: <code>min {y in selected != x} min(d(x,y) for x in selected)</code></li>
  </ul>
  
  <p>RC is minimum allowed <strong>d</strong>, and there is no absolute inequality between these two. But <code>RC &lt;= RE</code> is more desirable.</p>
  
  <h1>my little methods</h1>
  
  <p>For a little demonstration of that "performance measure," I generated 256 2-D points distributed uniformly or by standard normal distribution. Then I tried my top-down and bottom-up methods with them. And this is what I got:</p>
  
  <p><img src="https://i.stack.imgur.com/J8LM5.png" alt="bottom-up.norm">
  <img src="https://i.stack.imgur.com/pNp7B.png" alt="top-down.norm"></p>
  
  <p>RC is red, RE is blue. X axis is number of selected points. Did you think bottom-up could be as good? I thought so watching the animation, but it seems top-down is significantly better (look at the sparse region). Nevertheless, not too horrible given that it's much faster.</p>
  
  <p>Here I packed everything.</p>
  
  <p><a href="http://www.filehosting.org/file/details/352267/density_sampling.tar.gz" rel="nofollow noreferrer">http://www.filehosting.org/file/details/352267/density_sampling.tar.gz</a></p>