On finding non-intersecting paths in grids and its application in reconfiguring VLSI/WSI arrays

Abstract

The key result in this paper is an efficient algorithm for solving the following geometrical problem: given a set of points in a 2-dimensional grid; find a set of non-intersecting straight lines such that every line starts at a point and connects it to one of the boundaries of the grid. The algorithm presented here has quadratic (in the number of points) time complexity and is the first known polynomial time algorithm for this problem. Geometrical problems of this nature arise in the study of reconfigurable processor arrays, and the efficient algorithms developed in this paper can be used instead of the algorithms, based on exhaustive searches, that have been proposed in the literature.