Alcuni vedono nei matematici greci dei Sig. Jourdain della geometria algoritmica, ma questa disciplina ha davvero preso slancio solo a partire dagli anni Settanta, con l’avvento della progettazione assistita dal computer (CAD). Spesso si tratta allora di fornire rappresentazioni numeriche di forme tridimensionali. Emergono rapidamente molte nuove questioni, anche nella «semplice» geometria piana. In particolare, è essenziale gestire al meglio la complessità delle rappresentazioni. A questo scopo, la matematica mette a disposizione strumenti di portata universale, studiando in particolare diverse reticolazioni delle superfici e varie triangolazioni, per rispondere nel modo migliore alle delicate questioni poste dal passaggio dal continuo al discreto. Passiamo in rassegna alcuni problemi emblematici di questo affascinante e vivacissimo campo della ricerca matematica.
I vicini più prossimi ------------------------
Sia dato un insieme finito di punti del piano. Come trovare «rapidamente» i due punti più vicini tra loro? Quando il numero di punti non è molto elevato, si può rispondere intuitivamente e con scarso rischio di errore. Quando il numero di punti aumenta, occorre un approccio più organizzato. Si possono, in modo piuttosto ingenuo e brutale, calcolare tutte le distanze in gioco. Per n punti, ciò comporta n(n – 1)/2 calcoli e, in generale, si dice che la complessità temporale di questo metodo è dell’ordine di n 2.
Si può procedere diversamente con un sottile approccio ricorsivo. Si divide l’insieme dei punti in due parti con lo stesso numero di punti — o quasi, se tale numero è dispari — separate da una retta verticale, e si risolve ricorsivamente il problema per queste due parti. Resta poi da combinare i risultati ottenuti per i due insiemi. Alcuni accorgimenti permettono di limitare i calcoli in questa fase di combinazione (vedi riquadro). La complessità temporale di questo metodo è dell’ordine di n log(n), un guadagno tutt’altro che trascurabile quando il numero di punti diventa molto grande!
Il metodo può essere generalizzato allo spazio tridimensionale, o a dimensioni superiori, e offre così applicazioni concrete in molti ambiti, come il controllo del traffico aereo.