StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This a specific form of the <a href="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm" rel="nofollow">k-nearest neighbor</a> problem, namely where k=3. The cited page does not specify algorithmic complexity, but it's fairly obvious to see that a naive approach of computing the distance from the selected point to all other points, then computing the distance from that point to all other points, as well as the distance from our original point to the newly selected point is O(n<sup>k-1</sup>). Consider the pseudocode:</p> <pre><code>for pointB in searchSpace do: distanceAB := calculateDistance(pointA, pointB) for pointC in {searchSpace} - {pointB} do: distanceBC := calculateDistance(pointB, pointC) distanceCA := calculateDistance(pointC, pointA) if (distanceAB + distanceBC + distanceCA) < currentMin then: currentMin := distanceAB + distanceBC + distanceCA closestPoints := {pointA, pointB, pointC} </code></pre> <p>Note that we assume that <code>pointA</code> has already been removed from <code>searchSpace</code>. This is an O(n<sup>2</sup>) algorithm. Assuming dimension is relatively small, or that the function <code>calculateDistance</code> grows linearly or less with the dimension, this gives the solution in a decent time constraint. Optimizations could certainly be had, but they may not be required.</p> <p>If you want to see some real code, wikipedia has <a href="http://codingplayground.blogspot.com/2010/01/nearest-neighbour-on-kd-tree-in-c-and.html" rel="nofollow">many</a> <a href="http://www.leonardonascimento.com/en/knn.html" rel="nofollow">links</a> to <a href="http://compgeom.com/~stann" rel="nofollow">implementations</a>. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload