Simple wriggling is hard unless you are a fat hippo

I. Kostitsyna, V. Polishchuk

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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
Pages (from-to)93-110
Number of pages18
JournalTheory of Computing Systems
Volume50
Issue number1
DOIs
Publication statusPublished - 1 Jan 2012
Externally publishedYes

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