Aplicaciones de estructuras de datos a problemas matemáticos : Implementación del problema de seleccionar de un conjunto de puntos dado, el punto más cercano a otro punto dado.

Abstract

In the present work it is proposed to solve the nearest neighbor problem, which consists of finding from a set of n points in the plane, the one whose distance is minimum with a query point q external to the set. This problem is solved by implementing two algorithms. The first uses the brute force paradigm, in which all comparisons are made between the points of the set and the point q. The second algorithm proposed by Jon L. Bentley, organizes the points in a structure called 2d−Tree that facilitates the resolution of the problem efficiently. Algorithms are implemented in the programming language C++. To put them into execution, the instances were built simulating coordinates of points in the plane. Finally, different instances were executed, testing the algorithms and comparing them in terms of efficiency.