Rectilinear paths with minimum segment lengths

Given a set of nn open rectangles that represent obstacles in the Euclidean plane, we consider the problem of finding a shortest rectilinear path between two given points such that each segment of the path has a certain minimum length. A rectilinear path consists of horizontal and vertical segments only and may not intersect with an obstacle.We show how to solve the resulting shortest path problem with minimum segment lengths in polynomial time by constructing an extended Hanan grid of the instance first, and then run an adapted shortest path algorithm to find a respective solution. While the extended Hanan grid as basic underlying structure can be stored in O(n2)O(n2) space, the approach yields an O(n4logn)O(n4logn) time and O(n4)O(n4) space algorithm.The problem at hand typically arises in the area of VLSI design, where rectilinear paths are utilized to create wiring interconnects. There, the lithographic production process dictates certain minimum run lengths for the wires in order to avoid infeasible patterns. Another application arises in robot motion planning when acceleration and breaking distances need to be obeyed.