Simple wriggling is hard unless you are a fat hippo

I. Kostitsyna, V. Polishchuk

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

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.
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
PublisherSpringer
Chapter27
Pages272-283
Number of pages12
ISBN (Electronic)978-3-642-13122-6
ISBN (Print)978-3-642-13121-9
DOIs
Publication statusPublished - 2010
Externally publishedYes

Publication series

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

Fingerprint

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

Cite this