b'\n_START_ARTICLE_\nProblema do par de pontos mais pr\xc3\xb3ximo\n_START_PARAGRAPH_\nO problema do par de pontos mais pr\xc3\xb3ximo consiste em, dado um conjunto de n pontos num espa\xc3\xa7o m\xc3\xa9trico, encontrar os dois pontos do conjunto que possuem a menor dist\xc3\xa2ncia um do outro. A vers\xc3\xa3o em duas dimens\xc3\xb5es, para pontos num plano, estava entre os primeiros problemas geom\xc3\xa9tricos que foram tratados na origem do estudo de complexidade computacional de algoritmos geom\xc3\xa9tricos._NEWLINE_Se forem computadas as dist\xc3\xa2ncias entre todos os pares de pontos do conjunto, h\xc3\xa1 n(n-1)/2 computa\xc3\xa7\xc3\xb5es antes de ser poss\xc3\xadvel decidir inequivocamente qual o par que apresenta a menor dist\xc3\xa2ncia. Esse algoritmo \xc3\xa9 conhecido como for\xc3\xa7a bruta e tem complexidade de tempo O(n\xc2\xb2), ou seja, seu tempo de execu\xc3\xa7\xc3\xa3o \xc3\xa9 proporcional ao quadrado do n\xc3\xbamero de pontos do conjunto considerado. Por\xc3\xa9m, pesquisadores em geometria computacional descobriram que este problema pode ser resolvido em tempo O(n log n) em um espa\xc3\xa7o euclidiano ou espa\xc3\xa7o L\xe1\xb5\x96 de dimens\xc3\xa3o d fixa._NEWLINE_No modelo computacional que assume que a fun\xc3\xa7\xc3\xa3o ch\xc3\xa3o \xc3\xa9 computada em tempo constante, o problema pode ser resolvido em tempo de O(n log log n). Se for permitido o uso de escolhas aleat\xc3\xb3rias em conjunto com a fun\xc3\xa7\xc3\xa3o ch\xc3\xa3o, o problema pode ser resolvido em tempo O(n).'