Ranking intervals under visibility constraints
Edelsbrunner, Herbert
Overmars, Mark
Welzl, Emo
Hartman, Irith
Feldman, Jack
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 O(n 5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits.
Taylor & Francis
1990
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/4070
Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. Ranking intervals under visibility constraints. <i>International Journal of Computer Mathematics</i>. 1990;34(3-4):129-144. doi:<a href="https://doi.org/10.1080/00207169008803871">10.1080/00207169008803871</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1080/00207169008803871
info:eu-repo/semantics/altIdentifier/issn/0020-7160
info:eu-repo/semantics/altIdentifier/issn/1029-0265
info:eu-repo/semantics/closedAccess