On finding non-intersecting straightline connections of grid points to the boundary

Abstract

We consider the problem of determining whether it is possible to connect a given set of N points in an (m × n) rectangular 2D grid to the grid's boundary using N disjoint straight (horizontal or vertical) lines. If this is possible, we find such a set of lines. We provide an algorithm with either O(m + n) or O(N log N) complexity. In higher dimensions, the problem is NP-complete. We then extend our results to accommodate an additional constraint, namely forbidding connections in opposite directions that run next to one another. A solution to this problem can be used to provide a set of processor substitutions which reconfigure a fault-tolerant rectangular array of processing elements to avoid the faulty processors while retaining its important properties. © 1992.