HIIT seminar, Friday Feb 26, 10:15 a.m. (coffee from 10), Exactum B222
Dr. Valentin Polishchuk
Helsinki Institute for Information Technology HIIT Department of Computer Science University of Helsinki
Simple Wriggling is Hard unless you are a Fat Hippo
Abstract:
We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest path for a long snake amidst polygonal obstacles is NP-hard. On the positive side, we show that snake's problem is "length-tractable": if the snake is "fat", i.e., its length/width ratio is small, the shortest path can be computed in polynomial time.
This is a dry run of FUN'2010 talk.
Last updated on 23 Feb 2010 by Visa Noronen - Page created on 26 Feb 2010 by Visa Noronen