Ranking intervals under visibility constraints

H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, J. Feldman, International Journal of Computer Mathematics 34 (1990) 129–144.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ;
Abstract
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 ps∩t so that pu 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.
Publishing Year
Date Published
1990-01-01
Journal Title
International Journal of Computer Mathematics
Volume
34
Issue
3-4
Page
129 - 144
IST-REx-ID

Cite this

Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. Ranking intervals under visibility constraints. International Journal of Computer Mathematics. 1990;34(3-4):129-144. doi:10.1080/00207169008803871
Edelsbrunner, H., Overmars, M., Welzl, E., Hartman, I., & Feldman, J. (1990). Ranking intervals under visibility constraints. International Journal of Computer Mathematics, 34(3–4), 129–144. https://doi.org/10.1080/00207169008803871
Edelsbrunner, Herbert, Mark Overmars, Emo Welzl, Irith Hartman, and Jack Feldman. “Ranking Intervals under Visibility Constraints.” International Journal of Computer Mathematics 34, no. 3–4 (1990): 129–44. https://doi.org/10.1080/00207169008803871.
H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, and J. Feldman, “Ranking intervals under visibility constraints,” International Journal of Computer Mathematics, vol. 34, no. 3–4, pp. 129–144, 1990.
Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. 1990. Ranking intervals under visibility constraints. International Journal of Computer Mathematics. 34(3–4), 129–144.
Edelsbrunner, Herbert, et al. “Ranking Intervals under Visibility Constraints.” International Journal of Computer Mathematics, vol. 34, no. 3–4, Taylor & Francis, 1990, pp. 129–44, doi:10.1080/00207169008803871.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar