Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
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.
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008