A fast algorithm for connecting grid points to the boundary with nonintersecting straight lines

Abstract

We consider the problem of determining whether it is possible to connect a given set of N points in an (m × n) rectangular 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. Our yalgorithm can have either O(m + n) or O(N log N) complexity. We then extend our algorithm to accommodate an additional constraint, namely forbidding connections in opposite directions that run next to one another. A solution to this problem is equivalent to providing 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. We have also shown that the problem is NP-complete for 3-D grids as well as for partitioned 2-D grids.