<p>Your final sum will mostly be dominated by the largest addend. The simplest algorithm to exploit this could go like this (I cannot prove this):</p>

<ol>
<li>sort points descending by their nearest-neighbor distance</li>
<li>form pair of first entry and its nearest neighbor</li>
<li>remove pair from list</li>
<li>if list not empty goto 1.</li>
</ol>

<p>This should work very often.</p>

<p>Since you are essentially looking for a clustering algorithm for clusters of 2 <a href="http://arxiv.org/abs/0706.2569" rel="nofollow noreferrer">this link</a> or a search for <a href="http://scholar.google.com/scholar?hl=en&amp;q=+hadron+clustering+algorithm+shower" rel="nofollow noreferrer">clustering algorithms for jet reconstruction</a> might be interesting. People in the experimental particle physics community are working on heuristic algorithms for problems like this.</p>
Smallest sum of pairs
<p>Given <strong>2N-points</strong> in a <strong>2D-plane</strong>, you have to group them into <strong>N pairs</strong> such that the overall sum of distances between the points of all of the pairs is the minimum possible value.<strong>The desired output is only the sum.</strong></p>

<p>In other words, if <strong>a1,a2,..an</strong> are the  distances between points of first, second...and nth pair respectively, then <strong>(a1+a2+...an) should be minimum.</strong></p>

<p>Let us consider this test-case, if the <strong>2*5</strong> points are : 
<strong>{20,20},
{40, 20},
{10, 10},
{2, 2},
{240, 6},
{12, 12},
{100, 120},
{6, 48},
{12, 18},
{0, 0}</strong></p>

<p>The desired output is <strong>237</strong>.</p>

<p>This is not my homework,I am inquisitive about different approaches rather than brute-force.</p>