Simple Wriggling is Hard unless You Are a Fat Hippo

Details Simple Wriggling is Hard unless You Are a Fat Hippo Simple Wriggling is Hard unless You Are a Fat Hippo

2010-05-28

arxiv.org/abs/1005.5413v1

Computer Science

Computational Geometry

A shorter version is to be presented at FUN 2010

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Simple Wriggling is Hard unless You Are a Fat Hippo does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple Wriggling is Hard unless You Are a Fat Hippo, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Wriggling is Hard unless You Are a Fat Hippo will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86078