Summary: We consider the problem of finding the maximum number of nodes in a grid (from a given set of such nodes) that can be connected to the boundary of the grid by means of non-intersecting line segments parallel to the grid axes. The work is motivated from the VLSI/WSI array processor technology, and in particular, the single-track switch model for configurable array processors. The problem has been investigated by J. Bruck and V. P. Roychowdhury [J. Algorithms 12, No. 3, 516–529 (1991; Zbl 0724.90099)], who described an algorithm to find the maximum number of compatible connections of \(n\) given nodes in the grid in \(O(n^3)\) time and \(O(n^2)\) space. In this paper, we present methods that take advantage of the dependency of similar configurations and enable us to resolve the problem in \(O(n^2 \log n)\) time and \(O(n^2)\) space; instrumental in our algorithm is the use of a new type of priority search trees which is of interest in its own right.
For the entire collection see [Zbl 0816.00031].