Simple wriggling is hard unless you are a fat hippo

DOI10.1007/S00224-011-9337-4zbMATH Open1253.68155arXiv1005.5413OpenAlexW2176503837MaRDI QIDQ692941FDOQ692941

Authors: Irina Kostitsyna, Valentin Polishchuk 

Publication date: 6 December 2012

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

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.

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

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

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)

Cites Work

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

Cited In (1)

• The complexity of Snake and undirected NCL variants

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)