The digital world is no longer limited to text, sound and images, and digital representations of three-dimensional shapes play a central role in a wide range of fields. These include engineering, cartography, film and video games, architecture, cultural heritage preservation, oil exploration, medicine and drug design, to name but a few. Today, we can model the complex shapes of nature from the microscopic to the astronomical scale, statues by Michelangelo or cities. The shapes that can be represented on a computer are extremely varied, and the 3D data that needs to be processed is enormous. The design of efficient algorithms and the study of their complexity is critical. This is the subject of algorithmic geometry.
In the first part, this lecture studies the interactions between geometry and computation, and systematically examines several geometric structures that are fundamental from an algorithmic point of view. Probabilistic algorithms play a central role, and issues of robustness and numerical accuracy are discussed. It is necessary to rely on computational models that are simple enough to perform the analyses, but realistic enough to be useful in practice.
The second part looks at the representation of geometric shapes that can now be digitized. How can we build computer models of these complex shapes and guarantee the quality of approximations? The lecture begins with meshes of surfaces in three-dimensional space, and then moves on to higher-dimensional objects, which raise new topological and algorithmic questions. The techniques of algorithmic geometry can then be developed to approach data analysis from an original and fruitful geometric point of view.