En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclídeo fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos.[1]​[2]​
Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el mínimo", que requiere un tiempo  O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclídeo.[3]​ Este tiempo puede incluso ser mejorado: Si se asume que la función de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log  n).[4]​ Si además se permite utilizar aleatorización, el problema puede ser solucionado en tiempo O(n).[5]​[6]​