Determining maximum \(k\)-width-connectivity on meshes (Q685604)

Let \(I\) be a \(n\times n\) binary image storage in a \(n\times n\) mesh of processors with one pixel per processor. Image \(I\) is \(k\)-width-connected if, informally, between any pair of 1-pixels there exists a path of width \(k\) (composed of 1-pixels only). We consider the problem of determining the largest integer \(k\) such that \(I\) is \(k\)-width-connected, and present an optimal \(O(n)\) time algorithm for the mesh architecture.