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.
In VLSI numerous extensions and generalizations of the basic problem were considered. These include routing multiple paths, on several levels, and with different constraints and objectives. It is impossible to survey all literature on the subject; we will only mention the books @cite_14 @cite_16 .
@cite_14 @cite_16
1979696180 2150368068
We consider the existence and efficient construction of bounded curvature paths traversing constant-width regions of the plane, called corridors. We make explicit a width threshold τ with the property that (a) all corridors of width at least τ admit a unit-curvature traversal and (b) for any width w < τ there exist corridors of width w with no such traversal. Applications to the design of short, but not necessarily shortest, and high clearance, but not necessarily maximum clearance, curvature-bounded paths in general polygonal domains, are also discussed. This pioneering study of two-dimensional wiring patterns develops powerful algorithms for the physical design of VLSI circuits. Its homotopic approach to circuit layout advances the state of the art in wire routing and layout compaction, and will inspire future research. By viewing wires as flexible connections with fixed topology, the author obtains simple and efficient algorithms for CAD problems whose previous solutions employed, unreliable or inefficient heuristics."Single-Layer Wire Routing and Compaction" is the first rigorous treatment of homotopic layouts and the techniques for optimizing them. In a novel application of classical mathematics to computer science, Maley characterizes the ideal routing of a layout in terms of simple topological invariants. He derives practical algorithms from this theoretical insight. The algorithms and their underlying ideas are intuitive, widely applicable, and presented in a highly readable style.F. Miller Maley is a Research Associate in the Computer Science Department at Princeton University. "Single-Layer Wire Routing and Compaction" is included in the series Foundations of Computing, edited by Michael Garey and Albert Meyer.