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 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.