Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 20, 2014, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Stephan Seebacher
Given a polygonal domain P with holes in it and two points s,f in P, is there a thick s-f path? Specifically, can a thick snake slither from the startpoint s to the food f?
We prove that it is NP-hard to decide whether two points in P can be connected with a wire. On the positive side, we show that snake's problem is length-tractable: if the sanke is fat, i.e. its length/width ratio is small, the shortest path can be computed in polynomial time.
Automatic MiSe System Software Version 1.4803M | admin login