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 17171

Computational Geometry

( Apr 23 – Apr 28, 2017 )

(Click in the middle of the image to enlarge)

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

Organizers

Contact


Schedule

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.

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.

Copyright Otfried Cheong, Anne Driemel, and Jeff Erickson

Summary

Computational Gemoetry

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.

Seminar Topics

The emphasis of the seminar was 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 included broad survey talks on monitoring and shape data and on high-dimensional geometric computing, two focus areas that have seen exciting recent progress and that present 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.

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 held a lottery for the third time this year; the lottery allows to create space to invite younger researchers, rejuvenating the seminar, while keeping a large group of senior and well-known scholars involved. The seminar has now a more balanced attendance in terms of seniority and gender than in the past. This year, 47 researchers from various countries and continents attended the seminar, showing the strong interest of the community for this event. The feedback from participants was very positive. No other meeting in our field allows young researchers to meet with, get to know, and work with well-known and senior scholars to the extent possible at the Dagstuhl Seminar. We warmly thank the scientific, administrative and technical staff at Schloss Dagstuhl! Dagstuhl allows people to really meet and socialize, providing them with a wonderful atmosphere of a unique closed and pleasant environment, which is highly beneficial to interactions. Therefore, Schloss Dagstuhl itself is a great strength of the seminar.

Copyright Otfried Cheong, Anne Driemel, and Jeff Erickson

Participants
  • Mohammad Ali Abam (Sharif University of Technology - Tehran, IR) [dblp]
  • Tetsuo Asano (JAIST - Ishikawa, JP) [dblp]
  • Sang Won Bae (Kyonggi University, KR) [dblp]
  • Bahareh Banyassady (FU Berlin, DE) [dblp]
  • Ulrich Bauer (TU München, DE) [dblp]
  • Karl Bringmann (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Otfried Cheong (KAIST - Daejeon, KR) [dblp]
  • Man-Kwun Chiu (National Institute of Informatics - Tokyo, JP) [dblp]
  • Jinhee Chun (Tohoku University - Sendai, JP) [dblp]
  • Kenneth L. Clarkson (IBM Almaden Center - San Jose, US) [dblp]
  • Michael Gene Dobbins (Binghamton University, US) [dblp]
  • Anne Driemel (TU Eindhoven, NL) [dblp]
  • Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
  • Esther Ezra (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Kyle Jordan Fox (Duke University - Durham, US) [dblp]
  • Jie Gao (Stony Brook University, US) [dblp]
  • Joachim Gudmundsson (The University of Sydney, AU) [dblp]
  • Anna Gundert (Universität Köln, DE) [dblp]
  • Dan Halperin (Tel Aviv University, IL) [dblp]
  • David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
  • Michal Kleinbort (Tel Aviv University, IL) [dblp]
  • Christian Knauer (Universität Bayreuth, DE) [dblp]
  • Matias Korman (Tohoku University - Sendai, JP) [dblp]
  • Amer Krivosija (TU Dortmund, DE) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Till Miltzow (Free University of Brussels, BE) [dblp]
  • Joseph S. B. Mitchell (Stony Brook University, US) [dblp]
  • Wolfgang Mulzer (FU Berlin, DE) [dblp]
  • Aleksandar Nikolov (University of Toronto, CA) [dblp]
  • Zuzana Patáková (IST Austria - Klosterneuburg, AT) [dblp]
  • Jeff M. Phillips (University of Utah - Salt Lake City, US) [dblp]
  • Benjamin Raichel (University of Texas - Dallas, US) [dblp]
  • Abhishek Rathod (TU München, DE) [dblp]
  • Saurabh Ray (New York University - Abu Dhabi, AE) [dblp]
  • Marcel J. M. Roeloffzen (National Institute of Informatics - Tokyo, JP) [dblp]
  • Michael Sagraloff (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Alejandro Salinger (SAP SE - Walldorf, DE) [dblp]
  • Lena Schlipf (FernUniversität in Hagen, DE) [dblp]
  • Raimund Seidel (Universität des Saarlandes, DE) [dblp]
  • Fabian Stehn (Universität Bayreuth, DE) [dblp]
  • Monique Teillaud (INRIA Nancy - Grand Est, FR) [dblp]
  • André van Renssen (National Institute of Informatics - Tokyo, JP) [dblp]
  • Kevin Verbeek (TU Eindhoven, NL) [dblp]
  • Bei Wang Phillips (University of Utah - Salt Lake City, US) [dblp]
  • David P. Woodruff (IBM Almaden Center - San Jose, US) [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 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)
  • Dagstuhl Seminar 25201: Computational Geometry (2025-05-11 - 2025-05-16) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • Combinatorics
  • complexity
  • algorithms
  • geometric computing
  • implementation
  • applications
  • monitoring and shape data
  • high-dimensional computational geometry