b'\n_START_ARTICLE_\nProblema del par de puntos m\xc3\xa1s cercanos\n_START_PARAGRAPH_\nEn geometr\xc3\xada computacional, el problema del par de puntos m\xc3\xa1s cercano es un problema cl\xc3\xa1sico donde "Dados n puntos en un espacio m\xc3\xa9trico, se pide encontrar un par de puntos con la distancia m\xc3\xa1s peque\xc3\xb1a entre ellos". El problema del par de puntos m\xc3\xa1s cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistem\xc3\xa1tico de la complejidad computacional de algoritmos geom\xc3\xa9tricos.\xe2\x80\x8b\xe2\x80\x8b_NEWLINE_Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el m\xc3\xadnimo", que requiere un tiempo\xc2\xa0 O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclidiano.\xe2\x80\x8b Este tiempo puede incluso ser mejorado: Si asumimos que la funci\xc3\xb3n de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log\xc2\xa0 n).\xe2\x80\x8b Si adem\xc3\xa1s permitimos utilizar aleatorizaci\xc3\xb3n, el problema puede ser solucionado en tiempo O(n).\xe2\x80\x8b\xe2\x80\x8b\n_START_SECTION_\nAlgoritmo de fuerza bruta\n_START_PARAGRAPH_\nEl par m\xc3\xa1s cercano de puntos puede ser encontrado en tiempo proporcional a O(n^2) mediante una b\xc3\xbasqueda por fuerza bruta. Para ello habr\xc3\xada que computar las distancias entre las  combinaciones de pares de puntos, y elegir el par con la distancia m\xc3\xa1s peque\xc3\xb1a,._NEWLINE_minDist = infinito_NEWLINE_para i = 1 a longitud(P) - 1_NEWLINE_ para j = i + 1 a longitud(P)_NEWLINE_  dist = distancia(P[i], P[j])_NEWLINE_  si dist < minDist:_NEWLINE_   minDist = dist_NEWLINE_   closestPair = (i, j)_NEWLINE_devolver closestPair\n_START_SECTION_\nSoluci\xc3\xb3n mediante triangulaci\xc3\xb3n de Delaunay\n_START_PARAGRAPH_\nOtra forma de resolver el problema del par m\xc3\xa1s cercano es aprovechar la propiedad de la triangulaci\xc3\xb3n de Delaunay que indica que \xc2\xabcada v\xc3\xa9rtice de la triangulaci\xc3\xb3n siempre estar\xc3\xa1 conectado con su v\xc3\xa9rtice m\xc3\xa1s cercano\xc2\xbb. Por lo tanto, el par de puntos m\xc3\xa1s cercano puede ser determinado en tiempo lineal cuando disponemos de la triangulaci\xc3\xb3n de Delaunay (o el diagrama de Voronoi) calculando las longitudes de las aristas. Como el c\xc3\xa1lculo de la triangulaci\xc3\xb3n de Delaunay toma tiempo O(n log n), este proceso domina sobre el tiempo en encontrar la arista m\xc3\xa1s corta, y a su vez sirve de cota al tiempo necesario para encontrar el par m\xc3\xa1s cercano.'