Simple wriggling is hard unless you are a fat hippo

DOI10.1007/S00224-011-9337-4MaRDI QIDQ692941zbMATH OpenOpenAlexFDO

Authors Irina Kostitsyna, Valentin Polishchuk

Publication date 6 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.5413

zbMATH Keywords

computational geometryshortest pathsmotion planningVLSI

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

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.

Recommendations

• Walking around fat obstacles.
• Encomplexing the writhe
• Writhe in the stretch-twist-fold dynamo
• Self-avoiding walks with writhe
• Hopping Hoops Don't Hop
• Easy problems are sometimes hard

Cites work

• A near-linear algorithm for the planar segment-center problem
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• Curvature-bounded traversals of narrow corridors
• Forbidden patterns and unit distances
• Maximum thick paths in static and dynamic environments
• Planar Formulae and Their Uses
• Planning Algorithms
• THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS
• Theoretical Foundations of VLSI Design
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• Visiting a sequence of points with a bevel-tip needle

Cited in

(2)

• The complexity of Snake and undirected NCL variants
• The parameterized complexity of motion planning for snake-like robots

This page was built for publication: Simple wriggling is hard unless you are a fat hippo

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692941)