Fixed-parameter tractability and lower bounds for geometric optimization problems
- Speaker: Dr Panos Giannopoulos, School of Science and Technology, Department of Computer Science, Middlesex University.
- Date: Tuesday, 24 February 2015 from 16:00 to 17:00
- Location: Room 151, Birkbeck Main Building
In this talk, I will review recent and classical parameterized complexity results for hard geometric problems (usually studied within the realm of computational geometry), that is, problems where the solution space is constrained by collections of simple geometric input objects. This will include fundamental problems in the plane (e.g., covering, stabbing, TSP and related problems), but also higher dimensional problems and classical problems stemming from discrete geometry. Future research directions and several concrete open problems will also be presented. No previous knowledge of parameterized complexity or computational geometry will be assumed.