23. – 28. April 2017, Dagstuhl Seminar 17171
Auskunft zu diesem Dagstuhl Seminar erteilen
Susanne Bach-Bernhard zu administrativen Fragen
Marc Herbstritt zu wissenschaftlichen Fragen
Wir bitten die Teilnehmer uns bei der notwendigen Dokumentation zu unterstützen und Abstracts zu ihrem
Vortrag, Ergebnisse aus Arbeitsgruppen, etc. zur Veröffentlichung in unserer Serie Dagstuhl Reports
einzureichen über unser
Dagstuhl Reports Submission System.
(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)
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.
Seminar Topics. 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 geometry for monitoring and shape data. The combination of movement and geometry has always been an important topic in computational geometry, initially motivated by robotics and resulting in the study of kinetic data structures. With the advent of widely available location tracking technologies such as GPS sensors, trajectory analysis has become a topic in itself, which has connections to other classical topics in computational geometry such as shape analysis. Still, efficient technologies to perform the most basic operations are lacking. We need data structures supporting similarity queries on trajectory data and geometric clustering algorithms that can handle the infinite-dimensional geometry inherent in the data. A related type of data, namely time series data, has not received much attention in the computational geometry community, despite its universality and its close relation to trajectory data. Shedding light on the interconnections of these topics will promote new results in the field which will address these timely questions.
Computing in high-dimensional and infinite-dimensional spaces. The famous “curse of dimensionality” prevents exact geometric computations in high-dimensional spaces. Most of the data in science and engineering is high-dimensional, rendering classical geometric techniques, such as the sweepline approach, insufficient. One way to address this issue is to use sparsity, but it is not always easy to find a sparse representation of the data. The search of the most efficient representation and how to exploit this representation leads to dimension-reduction techniques, metric embeddings, and approximation algorithms. This line of research has strong ties to machine learning and discrete mathematics as well as computational geometry.
Creative Commons BY 3.0 DE
Otfried Cheong and Anne Driemel and Jeff Erickson
Dagstuhl Seminar Series
- 15111: "Computational Geometry" (2015)
- 13101: "Computational Geometry" (2013)
- 11111: "Computational Geometry" (2011)
- 09111: "Computational Geometry" (2009)
- 07111: "Computational Geometry" (2007)
- 05111: "Computational Geometry" (2005)
- 03121: "Computational Geometry" (2003)
- 01121: "Computational Geometry" (2001)
- 99102: "Computational Geometry" (1999)
- 9707: "Computational Geometry" (1997)
- 9511: "Computational Geometry" (1995)
- 9312: "Computational Geometry" (1993)
- 9141: "Computational Geometry" (1991)
- 9041: "Algorithmic Geometry" (1990)
- Data Structures / Algorithms / Complexity
- Geometric computing
- Monitoring and shape data
- High-dimensional computational geometry