About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
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.