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, CAD, robotics, computer vision, image processing, spatial databases, GIS, 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 and strong intellectual connections with other computing and mathematics disciplines.

The emphasis of the Dagstuhl Seminar is 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 new results in the field, the seminar will include broad survey talks with a special focus on two areas. The first is on parametrized algorithms in geometry and topology, and the second is on theoretical questions arising in Implementing Geometric Algorithms.

Parametrized Algorithms in Geometry and Topology

Certain algorithmic problems arising in geometric and topological settings seemed to be computational intractable, i.e., requiring exponential time in the worst case. However, yet in many cases they were often seemingly solvable more efficiently in practice. In the past several years, the community has started to develop a clear theory for how and when this can happen. Parametrized algorithms consider some parameter in the size of the solution (e.g., number of outliers, or topological features) and isolate the large (e.g., exponential) complexity in terms of only this component. This perspective has revitalized many core problems for which it had seemed no useful analysis was possible. By considering this recent progress on challenges in geometry and topology, we hope to reveal many more places where this perspective can be applied.

Theoretical Questions Arising in Implementing Geometric Algorithms

The interplay between theoretical algorithmic analysis, and the implementation of those algorithms has been a recurring pattern in computational geometry and topology. By actually implementing algorithms, it has revealed brushed over issues such as degeneracies or hidden constants or poor cache coherence. The identification of these implementation challenges has in turn driven the algorithmic modeling and design side of the community to refocus their efforts on managing these issues. And this has in turn led to impactful new theoretical results. This interaction is needed now more than ever as geometric algorithms are designed for applications in data analysis, robotics, physical modeling, and geographic information systems; yet there are sometimes hidden barriers keeping these designed algorithms from being widely adopted. This topic will aim to help identify ways that computational geometers and topologists can tune theoretical frameworks to adhere better to practical implementation demands.

Participants

Dagstuhl Seminars on computational geometry have been organized in a two year rhythm since a start in 1990. They have been extremely successful both in disseminating the knowledge and identifying new research thrusts. Many major results in computational geometry were first presented in Dagstuhl Seminars, and interactions among the participants at these seminars have led to numerous new results in the field. These seminars have also played an important role in bringing researchers together, fostering collaboration, and exposing young talent to the seniors of the field. They have arguably been the most influential meetings in the field of computational geometry. The organizers hold a lottery to create space to invite less senior researchers, while keeping a large group of senior and well-known scholars involved.

Creative Commons BY 4.0

Maarten Löffler, Eunjin Oh, and Jeff M. Phillips

• Oswin Aichholzer (TU Graz, AT) [dblp]
• Sayan Bandyapadhyay (Portland State University, US) [dblp]
• Benjamin Burton (The University of Queensland - Brisbane, AU) [dblp]
• Otfried Cheong (Universität Bayreuth, DE) [dblp]
• Mark de Berg (TU Eindhoven, NL) [dblp]
• Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
• Fedor V. Fomin (University of Bergen, NO) [dblp]
• Robert Ganian (TU Wien, AT) [dblp]
• Marc Glisse (Inria - Orsay, FR) [dblp]
• Joachim Gudmundsson (The University of Sydney, AU) [dblp]
• Dan Halperin (Tel Aviv University, IL) [dblp]
• Michael Hoffmann (ETH Zürich, CH) [dblp]
• Kristóf Huszár (TU Graz, AT) [dblp]
• Phillip Keldenich (TU Braunschweig, DE) [dblp]
• David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
• Francis Lazarus (CNRS - Grenoble, FR) [dblp]
• Jim Little (University of British Columbia - Vancouver, CA) [dblp]
• Maarten Löffler (Utrecht University, NL) [dblp]
• Gert Meijer (NHL Stenden Hogeschool - Leeuwarden, NL)
• Fabrizio Montecchiani (University of Perugia, IT) [dblp]
• Ian Munro (University of Waterloo, CA) [dblp]
• André Nusser (INRIA - Sophia Antipolis, FR) [dblp]
• Eunjin Oh (POSTECH - Pohang, KR) [dblp]
• Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
• Jeff M. Phillips (University of Utah - Salt Lake City, US) [dblp]
• Valentin Polishchuk (Linköping University, SE) [dblp]
• Raimund Seidel (Universität des Saarlandes - Saarbrücken, DE) [dblp]
• Jonathan Shewchuk (University of California - Berkeley, US) [dblp]
• Diane Souvaine (Tufts University - Medford, US) [dblp]
• Jonathan Spreer (University of Sydney, AU) [dblp]
• Frank Staals (Utrecht University, NL) [dblp]
• Birgit Vogtenhuber (TU Graz, AT) [dblp]
• Hubert Wagner (University of Florida - Gainesville, US) [dblp]
• Alexandra Weinberger (FernUniversität in Hagen, DE)
• Carola Wenk (Tulane University - New Orleans, US) [dblp]
• Mathijs Wintraecken (INRIA - Sophia Antipolis, FR) [dblp]
• Alexander Wolff (Universität Würzburg, DE) [dblp]
• Yelena Yuditsky (ULB - Brussels, BE) [dblp]
• Ling Zhou (Duke University - Durham, US) [dblp]