Abstract
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 ([4]). The problem has been investigated by Bruck and Roychowdhury, 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 ([2]). 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 2log 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.
Work supported by the National Science Foundation (NSF/DMS-8920161), the Dept. of Energy (DOE/DE-FG02-92ER25137), Minnesota Technology, Inc., and the Univ. of Minnesota.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Y. Birk and J.B. Lotspiech, “A Fast Algorithm for Connecting Grid Points to the Boundary with Nonintersecting Straight Lines,” Proc. 2nd Annual Symp. on Discrete Algorithms (1991), 465–474.
J. Bruck and V.P. Roychowdhury, “How to Play Bowling in Parallel on the Grid,” Journal of Algorithms12 (1991), 516–529.
K. Hwang and F.A. Briggs, “Computer Architecture and Parallel Processing,” McGraw Hill, New York, 1985.
S.Y. Kung, S.N. Jean, and C.W. Chang, “Fault-Tolerant Array Processors using Single-Track Switches,” IEEE Trans. on Computers38 (1989), 501–514.
E.M. McCreight, “Priority Search Trees,” SIAM Journal on Computing14 (1985), 257–276.
L. Palios, “Connecting Grid Points to the Boundary of the Grid by Means of Non-intersecting Line Segments,” Report GCG56, The Geometry Center, 1993.
R. Raghavan, J. Cohoon, and S. Sahni, “Manhattan and Rectilinear Wiring,” Tech. Report 81-5, Computer Science Dept., University of Minnesota, 1981.
V.P. Roychowdhury and J. Bruck, “On Finding Non-intersecting Paths in Grids and its Application in Reconfiguring VLSI/WSI Arrays,” Proc. 1st Annual Symp. on Discrete Algorithms (1990).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Palios, L. (1994). Connecting the maximum number of grid nodes to the boundary with non-intersecting line segments. In: Schmidt, E.M., Skyum, S. (eds) Algorithm Theory — SWAT '94. SWAT 1994. Lecture Notes in Computer Science, vol 824. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58218-5_24
Download citation
DOI: https://doi.org/10.1007/3-540-58218-5_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58218-2
Online ISBN: 978-3-540-48577-3
eBook Packages: Springer Book Archive