TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23221

Computational Geometry

( May 29 – Jun 02, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23221

Organizers

Contact


Schedule

Summary

This Dagstuhl Seminar constituted a biennial gathering of computational geometers at the Dagstuhl venue to share recent results, and further research on some of the most important problems of the time in that field. This year, the seminar focused on two of the most exciting sub-areas within computational geometry: (1)~reconfiguration, and (2)~processing and applications of uncertain and probabilistic geometric data. Within the reconfiguration topic, two overview talks focused on triangulation and graph reconfiguration, and on how reconfiguration plays a role in puzzle complexity. A highlight of the seminar were the set of three-dimensional reconfiguration puzzles brought by Ryuhei Uehara, which occupied attendees endlessly, and brought the challenge of modelling such puzzles to life. In the second theme on uncertainty, one overview talk covered uncertainty issues in spatial data, and another focused on how uncertainty connects to differential privacy in geometric settings. Other results were shared by participants connecting these topics to diverse motivations ranging from robotics to data analysis to graph drawing. Exciting open problems were proposed, and were used to focus the discussion for the span of the seminar.

Copyright Siu-Wing Cheng, Maarten Löffler, and Jeff M. Phillips

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, 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 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 Dagstuhl Seminar will include broad survey talks with a special focus on two areas. First, processing and application of uncertain and probabilistic geometric data. Second, is reconfiguration. Both topics have seen deep recent technical development and connections with geometric application domains such as data management, robotics, and graph drawing.

Processing and Applications of Uncertain and Probabilistic Geometric Data
As uncertain and probabilistic data is produced in increasing volume by sensing devices, the processing and applications of such data is becoming an emerging theme. Several basic problems in computational geometry such as convex hull and minimum spanning tree have been reexamined in this new setting. The processing of uncertain or probabilistic data in privacy, geometric optimization, nearest neighbor search, and range searching have also opened up new research directions. The topic of uncertain and probabilistic geometric data will also connect computational geometry to other disciplines, such as database and machine learning, in which there are also more research works with similar themes.

Reconfiguration
Reconfiguration problems have been long studied in combinatorial mathematics. There is a long history of research on the structure of reconfiguration graphs of discrete geometric and topological objects, such as for instance flip graphs of triangulations or rectangular subdivisions, Reidemeister graphs in knot theory, etc. Indeed, many researchers in computational geometry who are also active in adjacent fields such as graph theory and combinatorial topology have long investigated such reconfiguration problems.

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.

Copyright Siu-Wing Cheng, Maarten Löffler, and Jeff M. Phillips

Participants
On-site
  • Peyman Afshani (Aarhus University, DK) [dblp]
  • Hee-Kap Ahn (POSTECH - Pohang, KR) [dblp]
  • Håvard Bakke Bjerkevik (TU Graz, AT)
  • Kevin Buchin (TU Dortmund, DE) [dblp]
  • Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
  • Siu-Wing Cheng (HKUST - Kowloon, HK) [dblp]
  • Guilherme D. da Fonseca (Aix-Marseille University, FR)
  • Vincent Despré (LORIA - Nancy, FR) [dblp]
  • Ioannis Emiris (Athena Research Center - Maroussi, GR) [dblp]
  • Linda Kleist (TU Braunschweig, DE) [dblp]
  • Fabian Klute (UPC Barcelona Tech, ES)
  • Maarten Löffler (Utrecht University, NL and Tulane University - New Orleans, US) [dblp]
  • Zuzana Masárová (Wien, AT)
  • Bojan Mohar (Simon Fraser University - Burnaby, CA) [dblp]
  • Alexander Munteanu (TU Dortmund, DE)
  • Martin Nöllenburg (TU Wien, AT) [dblp]
  • Eunjin Oh (POSTECH - Pohang, KR) [dblp]
  • Irene Parada (UPC Barcelona Tech, ES)
  • Salman Parsa (DePaul Uniersity - Chicago, US)
  • Zuzana Patáková (Charles University - Prague, CZ) [dblp]
  • Jeff M. Phillips (University of Utah - Salt Lake City, US) [dblp]
  • Aleksandr Popov (TU Eindhoven, NL)
  • Ioannis Psarros (Athena Research Center, GR)
  • Manfred Scheucher (TU Berlin, DE) [dblp]
  • Raimund Seidel (Universität des Saarlandes - Saarbrücken, DE) [dblp]
  • Willem Sonke (TU Eindhoven, NL)
  • Subhash Suri (University of California - Santa Barbara, US) [dblp]
  • Monique Teillaud (INRIA Nancy - Grand Est, FR) [dblp]
  • Konstantinos Tsakalidis (University of Liverpool, GB)
  • Torsten Ueckerdt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Ryuhei Uehara (JAIST - Ishikawa, JP) [dblp]
  • Birgit Vogtenhuber (TU Graz, AT) [dblp]
  • Hubert Wagner (University of Florida - Gainesville, US) [dblp]
  • Emo Welzl (ETH Zürich, CH) [dblp]
  • Carola Wenk (Tulane University - New Orleans, US) [dblp]
  • Sang Duk Yoon (Sungshin Women's University - Seoul, KR)
  • Yelena Yuditsky (UL - Brussels, BE) [dblp]
Remote:
  • Anna Lubiw (University of Waterloo, CA) [dblp]

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 25201: Computational Geometry (2025-05-11 - 2025-05-16) (Details)

Classification
  • Computational Geometry
  • Data Structures and Algorithms
  • Discrete Mathematics

Keywords
  • combinatorics
  • algorithms
  • geometric computing
  • uncertainty
  • reconfiguration