08.03.15 - 13.03.15, Seminar 15111

Computational Geometry

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

Computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological problems, which arise naturally in a wide range of areas, including computer graphics, robotics, geographic information systems, molecular biology, sensor networks, machine learning, data mining, scientific computing, theoretical computer science, and pure mathematics. Computational geometry is a vibrant and mature field of research, with several dedicated international conferences and journals, significant real-world impact, and strong intellectual connections with other computing and mathematics disciplines.

The emphasis of the seminar will be on presenting recent developments in computational geometry, as well as identifying new challenges, opportunities, and connections to other fields of computing. In addition to the usual broad coverage of emerging results in the field, the seminar will include invited survey talks on two broad and overlapping focus areas that cover a wide range of both theoretical and practical issues in geometric computing. Both focus areas have seen exciting recent progress and offer numerous opportunities for further cross-disciplinary impact.

Computational topology. Over the last decade, computational topology has grown from an important subfield of computational geometry into a mature research area in its own right. Results in this field combine classical mathematical techniques from combinatorial, geometric, and algebraic topology with algorithmic tools from computational geometry and optimization. Key developments in this area include algorithms for modeling and reconstructing surfaces from point-cloud data, algorithms for shape matching and classification, topological graph algorithms, new generalizations of persistent homology, practical techniques for experimental low-dimensional topology, and new fundamental results on the computability and complexity of embedding problems. These results have found a wide range of practical applications in computer graphics, computer vision, robotics, sensor networks, molecular biology, data analysis, and experimental mathematics.

Geometric data analysis. Geometric data sets are being generated at an unprecedented scale from many different sources, including digital video cameras, satellites, sensor networks, and physical simulations. The need to manage, analyze, and visualize dynamic, large-scale, high-dimensional, noisy data has raised significant theoretical and practical challenges not addressed by classical geometric algorithms. Key developments in this area include new computational models for massive, dynamic, and distributed geometric data; new techniques for effective dimensionality reduction; approximation algorithms based on coresets and other sampling techniques; algorithms for noisy and uncertain geometric data; and geometric algorithms for information spaces. Results in this area draw on mathematical tools from statistics, linear algebra, functional analysis, metric geometry, geometric and differential topology, and optimization, and they have found practical applications in spatial databases, clustering, shape matching and analysis, machine learning, computer vision, and scientific visualization.