k-Nearest Neighbours and Quadtrees

k-nearest neighbours belongs to the simpler classification algorithms and is often used to introduce the subject. One of its drawbacks is the computational cost of determining neighbours: For one point, the naive approach computes distances to all other n1n-1 points. This behaviour can become slow, for example when continuously running the procedure in real-time. One approach to speed up computation is to search fewer nodes, which can be achieved with tree structures.

The interactive app illustrates how quadtrees can be searched to reduce computational cost. The intensity of the squares' colors depicts the depth of the searched tree.