Computational Geometry

Motivation

The field of computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological problems, which arise in a wide range of areas, including computer graphics, CAD, robotics computer vision, image processing, spatial databases, GIS, molecular biology, and sensor networks. Since the mid 1980s, computational geometry has arisen as an independent field, with its own international conferences and journals.

In the early years mostly theoretical foundations of geometric algorithms were laid and fundamental research remains an important issue in the field. Meanwhile, as the field matured, researchers have started paying close attention to applications and implementations of geometric and topological algorithms. Several software libraries for geometric computation (e.g. LEDA, CGAL, CORE) have been developed. Remarkably, this emphasis on applications and implementations has emerged from the originally theoretically oriented computational geometry community itself, so many researchers are concerned now with theoretical foundations as well as implementations.

The seminar will focus on a variety of topics. We plan to have one or two in-depth presentations (60 minutes each) for these topics, accompanied by short presentations of recent work and intensive discussions.

• Theoretical foundations of computational geometry lie in combinatorial geometry and its algorithmic aspects. They are of an enduring relevance for the field, particularly the design and the analysis of efficient algorithms require deep theoretical insights.
• Geometric Computing has become an integral part of the research in computational geometry. Besides general software design questions, especially robustness of geometric algorithms is important. Several methods have been suggested and investigated to make geometric algorithms numerically robust while keeping them efficient, which lead to interaction with the field of computer algebra, numerical analysis, and topology.
• Computational topology concentrates on the properties of geometric objects that go beyond metric represenation: modeling and reconstruction of surfaces, shape similarity and classification, and persistence are key concepts with applications in molecular biology, computer vision, and geometric databases.
• In its early years, computational geometry concentrated on low dimensions. High-dimensional data come very important recently, in particular, in work related to machine learning and data analysis. Standard solutions suffer from the curse of dimensionality. This has led to extensive work on dimension-reduction and embedding techniques.
• Various applications such as robotics, GIS, or CAD lead to interesting variants of the classical topics originally investigated, including convex hulls, Voronoi diagrams and Delaunay triangulations, and geometric data structures. For example, Voronoi diagrams and nearest-neighbor data structures under various metrics have turned out to be useful for many applications and are being investigated intensively.
• Massive geometric data sets are being generated by networks of sensors at unprecedented spatial and temporal scale. How to store, analyze, query, and visualize them has raised several algorithmic challenges. New computational models have been proposed to meet these challenges, e.g., streaming model, communication-efficient algorithms, and maintaining geometric summaries.