Inspecting a Set of Strips Optimally

摘要

We consider a set of axis-parallel nonintersecting strips in the plane. An observer starts to the left of all strips and ends to the right, thus visiting all strips in the given order. A strip is inspected as long as the observer is inside the strip. How should the observer move to inspect all strips? We use the path length outside a strip as a quality measure which should be minimized. Therefore, we would like to find a directed path that minimizes the maximal measure among all strips. We present an optimal algorithm designed according to the structural properties of the optimal solution.