Fast calculation is important, but reliable calculation is perhaps even more so. This question is less simple than it seems. The pioneers of algorithmic geometry analyzed the performance of algorithms on the assumption that all operations on real numbers could be performed exactly at unit cost. Such a computational model allows us to focus on the asymptotic estimation of algorithm complexity, but completely ignores the fact that computers work with finite representations of numbers.
This is particularly problematic in algorithmic geometry, where we seek to construct Combinatorics structures (such as the convex envelope of a finite set of points) by relying on numerical operations linked to the folding of these structures. This arithmetical dimension of geometric calculus has long been a brake on the spread of algorithmic geometry techniques.
This lecture distinguishes between predicates and geometric constructions, and analyzes the need for numerical precision in some fundamental geometric algorithms. A key question is the exact evaluation of the sign of polynomials whose variables are the input data. All algorithms solving the same problem do not necessarily have the same algebraic complexity, as shown by the example of calculating the arrangement of plane segments. Another example is given by the witness complex, which uses only polynomials of degree 2, but can, under certain conditions, approximate a Delaunay triangulation whose degree is d + 2 and depends on the dimension of the workspace. Theoretical and practical developments in geometric calculation have led to spectacular advances, of which the CGAL software library is a prime example. Today, it is possible to certify the results provided by most fundamental geometric algorithms without significantly degrading their performance.
