Algunos ven en los matemáticos griegos unos Sr. Jourdain de la geometría algorítmica, pero esta no despegó realmente hasta la década de 1970, con la llegada del diseño asistido por ordenador (CAD). Entonces se trataba a menudo de proporcionar representaciones numéricas de formas tridimensionales. Pronto surgieron muchas cuestiones nuevas, incluso en la geometría plana «simple». Resulta esencial, en particular, gestionar del mejor modo posible la complejidad de las representaciones. Para ello, las matemáticas aportan herramientas de alcance universal, mediante el estudio, entre otras cosas, de distintos mallados de superficies y triangulaciones, con el fin de responder lo mejor posible a las delicadas cuestiones que plantea el paso de lo continuo a lo discreto. Repasemos algunas cuestiones emblemáticas de este apasionante y muy activo ámbito de la investigación matemática.
Los vecinos más próximos ------------------------
Considere un conjunto finito de puntos del plano. ¿Cómo encontrar «rápidamente» los dos puntos que están más próximos entre sí? Cuando el número de puntos no es muy elevado, podemos responder intuitivamente y sin gran riesgo de equivocarnos. Cuando aumenta el número de puntos, se impone un enfoque más organizado. De manera bastante ingenua y directa, se pueden calcular todas las distancias implicadas. Para n puntos, esto supone n(n – 1)/2 cálculos y, en conjunto, se dice que la complejidad temporal de este método es del orden de n 2.
También puede procederse de otro modo, mediante un sutil enfoque recursivo. Se divide el conjunto de puntos en dos partes con el mismo número de puntos —o casi, si este número es impar—, separadas por una recta vertical, y se resuelve recursivamente el problema para ambas partes. Después hay que combinar los resultados obtenidos para estos dos conjuntos. Algunos trucos permiten limitar los cálculos en esta etapa de combinación (véase el recuadro). La complejidad temporal de este método es del orden de n log(n), ¡una mejora que dista mucho de ser anecdótica cuando el número de puntos se hace muy grande!
El método puede generalizarse al espacio tridimensional —o a dimensiones superiores— y ofrece así aplicaciones concretas en numerosos ámbitos, como el control aéreo.