Fixed-Parameter Computational Geometry

Location: Lorentz Center@Oort, Leiden
Date: 4-8 April 2016

Organizers: Mark de Berg (TU/e), Hans Bodlaender (UU), Michael Fellows (Darwin, NT, Australia), Christian Knauer (Bayreuth, Germany)

Number of participants: 55

From 4 to 8 April the workshop Fixed-Parameter Computational Geometry took place in the Lorentz Center in Leiden.


Description and aims

Algorithms and data structures form a key component of any software system. Many algorithmic problems arising in practice are intractable, which means there are no fast algorithm solving these
problems optimally on all problem instances. The area of fixed-parameter tractability tries to gain more insight into such problems, by analyzing them in terms of some well-defined parameter(s) that capture the difficulty of the problem. In many applications, algorithms are needed for problems involving spatial data. Computational geometry is the area within algorithm research dealing with spatial data. This workshop brought together researchers from the areas of computational geometry and fixed-parameter tractability, to advance the study of intractable problems on spatial data.



The workshop consisted of a number of tutorials, a number of talks by participants explaining recent work, and open problem sessions and progress reports, with an outlook lecture at the end of the workshop. After the first open problem session, participants formed groups to work on the stated open problems.



During the workshop, the participants worked in small teams on a number of open problems. According to a small survey by email many of the participants are currently working on joint papers with other participants, based upon work that was initiated / done during the week of the workshop in the Lorentz center.