Dagstuhl Seminar 25201
Computational Geometry
( May 11 – May 16, 2025 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25201
Organizers
- Maarten Löffler (Utrecht University, NL)
- Eunjin Oh (POSTECH - Pohang, KR)
- Jeff M. Phillips (University of Utah - Salt Lake City, US)
Contact
- Michael Gerke (for scientific matters)
- Simone Schilke (for administrative matters)
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
Related Seminars
- Dagstuhl Seminar 9041: Algorithmic Geometry (1990-10-08 - 1990-10-12) (Details)
- Dagstuhl Seminar 9141: Computational Geometry (1991-10-07 - 1991-10-11) (Details)
- Dagstuhl Seminar 9312: Computational Geometry (1993-03-22 - 1993-03-26) (Details)
- Dagstuhl Seminar 9511: Computational Geometry (1995-03-13 - 1995-03-17) (Details)
- Dagstuhl Seminar 9707: Computational Geometry (1997-02-10 - 1997-02-14) (Details)
- Dagstuhl Seminar 99102: Computational Geometry (1999-03-07 - 1999-03-12) (Details)
- Dagstuhl Seminar 01121: Computational Geometry (2001-03-18 - 2001-03-23) (Details)
- Dagstuhl Seminar 03121: Computational Geometry (2003-03-16 - 2003-03-21) (Details)
- Dagstuhl Seminar 05111: Computational Geometry (2005-03-13 - 2005-03-18) (Details)
- Dagstuhl Seminar 07111: Computational Geometry (2007-03-11 - 2007-03-16) (Details)
- Dagstuhl Seminar 09111: Computational Geometry (2009-03-08 - 2009-03-13) (Details)
- Dagstuhl Seminar 11111: Computational Geometry (2011-03-13 - 2011-03-18) (Details)
- Dagstuhl Seminar 13101: Computational Geometry (2013-03-03 - 2013-03-08) (Details)
- Dagstuhl Seminar 15111: Computational Geometry (2015-03-08 - 2015-03-13) (Details)
- Dagstuhl Seminar 17171: Computational Geometry (2017-04-23 - 2017-04-28) (Details)
- Dagstuhl Seminar 19181: Computational Geometry (2019-04-28 - 2019-05-03) (Details)
- Dagstuhl Seminar 21181: Computational Geometry (2021-05-02 - 2021-05-07) (Details)
- Dagstuhl Seminar 23221: Computational Geometry (2023-05-29 - 2023-06-02) (Details)
Classification
- Computational Geometry
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- Combinatorics
- Complexity
- Algorithms
- Geometric Computing
- Implementation
