Lorentz Center - Geometric Algorithms in the Field from 23 Jun 2014 through 27 Jun 2014
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Geometric Algorithms in the Field
    from 23 Jun 2014 through 27 Jun 2014


Geometric Algorithms in the Field

June 23 – 27 2014 @ Oort



Workshop topic and aim


Geometric algorithms are used to solve geometric problems: problems that involve spatial data, points and objects that live in two or more dimensions. They are important, and have a myriad of very different applications. At the same time, they are also complex and highly specialized. Computational geometry emerged in the 70s as an independent research field that studies the theory behind geometric algorithms. Over the last four decades, a rich theory has evolved, spanning many subfields and communities world-wide. The theory developed in computational geometry has already had a large impact on many application areas. However, there is an even larger potential for many more areas. Part of the reason for this unutilized potential is limited awareness and communication between researchers in computational geometry and people active in various application domains.


The aim of the proposed workshop was two-fold. On the one hand, we wished to raise awareness of the potential for geometric algorithms by showcasing successful application of geometric algorithms in practical situations, both to researchers in computational geometry and to application practitioners. On the other hand, we wanted to stimulate discussion between geometers and domain experts, to identify novel ways to apply existing theory to solve real-world geometric problems, and to focus the direction of geometric research by discovering problems for which the existing theory is insufficient. To focus the workshop, we selected four representative key application domains: robotics & automation, information visualization, meshing & surface reconstruction, and geographical information analysis.


Workshop format


The workshop was planned during one five-day week, in which several activities were planned to reach the workshop objectives.


The first one-and-a-half days were reserved for introducing the participants and workshop objectives, and we scheduled four overview presentations on each of the key application domains. Each presentations was allotted 60 minutes and most were given by a pair of speakers: one researcher in core computational geometry who has done work motivated from the respective application domain in the past, and one applied researcher in the same domain. Each talk introduced the domain and the specific geometric challenges in it to the other participants, and pointed at potentially interesting directions for further research.


During the remainder of the workshop, the main activity consisted of collaborative research in sub-groups of 5-10 people that focused on concrete challenges. After the third day, we switched group compositions, to give participants a chance to work on different topics. There were two plenary progress report sessions, after the third day and at the end of the workshop, in which the individual findings of the groups were presented and discussed among all participants.


Additionally, we scheduled four longer keynote presentations by domain experts on each of the application domains that highlighted successful existing applications of geometric algorithms to practical problems. These talks were distributed over the week.


Workshop outcomes and evaluation


The first goal of the workshop was to raise awareness of the potential of computational geometry. It is hard give an objective measure for this, but we believe that the workshop was very successful in this respect and the objective was achieved. The plenary talks were well attended, and sparked informal discussions throughout the week.

The second objective was to initiate future collaborations in the four selected application fields. We are aware of several concrete initiatives that started during the workshop:

        Many measures for trajectory similarity have been introduced over the years, both in the GIS and computational geometry fields. A group of participants has done a comparative study of all of these different measures, which is intended to be submitted to the PLOS One journal.

        Bringing together researchers from computational geometry and different subareas of robotics has triggered a number of followup exchanges to pursue further collaborations between geometry and robot navigation. Of particular interest are the interplay between distributed algorithmic methods, robust geometric computation, and swarm robotics, as well as the connections between exact methods from discrete optimization methods for solving NP-hard problems, computational geometry, and robot navigation for individual robots. The Lorentz workshop has made it possible to build a network of researchers with these varying backgrounds, which will undoubtedly spawn a number of future publications.

        In information visualisation, an important task is to show trends and important features in ensembles of data series, for example different weather predictions. A group of participants is adapting techniques from computational geometry to solve this problem, with the aim to submit to the INFOVIS conference.

        There is a fundamental geometric structure called the "constrained Delaunay triangulation" which is used in finite element mesh generation to constrain specified edges to appear in a Delaunay-like mesh.  There is another fundamental geometric structure called the "restricted Delaunay triangulation" that defines Delaunay-like triangulations on smooth surfaces em-bedded in three-dimensional space.  No previous attempts have been made to combine the two, but the combination has clear potential to help construct surface meshes in which speci-fied edges are constrained to appear.  At the workshop, a group of participants worked out a conceptual basis for defining such triangulations.  Subsequent to the workshop, they are still actively engaged in deriving the sampling conditions that will guarantee the existence of a well-formed restricted constrained Delaunay triangulation (RCDT), and algorithms for con-structing RCDTs.  We believe that RCDTs will be useful in computer graphics and boundary element methods.





The Lorentz Center is thanked for facilitating this workshop, and the staff of the Lorentz Center for their assistance in arranging and running the workshop. The workshop was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 (VICI Bettina Speckmann).


Sándor Fekete (Braunschweig, Germany)   

Maarten Löffler (Utrecht, The Netherlands)   

Jonathan Shewchuk (Berkeley, USA)   

Bettina Speckmann (Eindhoven, The Netherlands)   

Jo Wood (London, United Kingdom)