Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
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.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989