Some see the Greek mathematicians as the Monsieur Jourdains of computational geometry, but the field only really took off in the 1970s with the advent of computer-aided design (CAD). The task was often to provide digital representations of three-dimensional shapes. Many new questions quickly arose, even in "simple" plane geometry. In particular, it was essential to manage the complexity of these representations as efficiently as possible. Mathematics provides broadly applicable tools for this purpose, notably by studying different surface meshes and triangulations to address the delicate transition from the continuous to the discrete. Let's look at a few emblematic questions in this fascinating and highly active field of mathematical research.
The closest-pair problem ------------------------
Take a finite set of points in the plane. How can we find the two closest points "quickly"? When there are relatively few points, we can answer intuitively, with little risk of error. As their number grows, a more systematic approach is needed. One fairly naive, brute-force method is to calculate every distance involved. For n points, this requires n(n – 1)/2 calculations; the running time of this method is therefore on the order of n 2.
A subtler recursive approach is also possible. We divide the set of points into two subsets containing the same number of points—or almost the same number if the total is odd—separated by a vertical line, then solve the problem recursively for each subset. The two results must then be combined. A few tricks limit the number of calculations required at this combining stage (see box). The time complexity of this method is of order n log(n), a substantial improvement when the number of points becomes very large!
The method extends to three dimensions—or more—and then has practical applications in many fields, including air traffic control.