Simple wriggling is hard unless you are a fat hippo

I. Kostitsyna, V. Polishchuk

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationFun with algorithms
Subtitle of host publication5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings
EditorsP. Boldi, L. Gargano
Place of PublicationBerlin
Number of pages12
ISBN (Electronic)978-3-642-13122-6
ISBN (Print)978-3-642-13121-9
Publication statusPublished - 2010
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743


Dive into the research topics of 'Simple wriggling is hard unless you are a fat hippo'. Together they form a unique fingerprint.

Cite this