Matthew A Grayson
Journal of Complexity
Let S be a set of n closed intervals on the x-axis. A ranking assigns to each interval, s, a distinct rank, p(s)∈ {1, 2,…, n}. We say that s can see t if p(s)<p(t) and there is a point p∉ s∩ t so that p∉u for all u with p(s)<p(u)<p(t). It is shown that a ranking can be found in time O(n log n) such that each interval sees at most three other intervals. It is also shown that a ranking that minimizes the average number of endpoints visible from an interval can be computed in time 0(n5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits. © 1990, Taylor & Francis Group, LLC. All rights reserved.
Matthew A Grayson
Journal of Complexity
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications