[{"main_file_link":[{"url":"https://www.tandfonline.com/doi/abs/10.1080/00207169008803871"}],"title":"Ranking intervals under visibility constraints","doi":"10.1080/00207169008803871","year":"1990","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","oa_version":"None","_id":"4070","publication_identifier":{"issn":["0020-7160"],"eissn":["1029-0265"]},"extern":"1","volume":34,"publist_id":"2051","date_updated":"2022-02-21T13:19:52Z","article_processing_charge":"No","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"last_name":"Overmars","full_name":"Overmars, Mark","first_name":"Mark"},{"last_name":"Welzl","full_name":"Welzl, Emo","first_name":"Emo"},{"first_name":"Irith","last_name":"Hartman","full_name":"Hartman, Irith"},{"full_name":"Feldman, Jack","last_name":"Feldman","first_name":"Jack"}],"abstract":[{"lang":"eng","text":"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."}],"publication_status":"published","citation":{"ieee":"H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, and J. Feldman, “Ranking intervals under visibility constraints,” <i>International Journal of Computer Mathematics</i>, vol. 34, no. 3–4. Taylor &#38; Francis, pp. 129–144, 1990.","apa":"Edelsbrunner, H., Overmars, M., Welzl, E., Hartman, I., &#38; Feldman, J. (1990). Ranking intervals under visibility constraints. <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/00207169008803871\">https://doi.org/10.1080/00207169008803871</a>","chicago":"Edelsbrunner, Herbert, Mark Overmars, Emo Welzl, Irith Hartman, and Jack Feldman. “Ranking Intervals under Visibility Constraints.” <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis, 1990. <a href=\"https://doi.org/10.1080/00207169008803871\">https://doi.org/10.1080/00207169008803871</a>.","ama":"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>","mla":"Edelsbrunner, Herbert, et al. “Ranking Intervals under Visibility Constraints.” <i>International Journal of Computer Mathematics</i>, vol. 34, no. 3–4, Taylor &#38; Francis, 1990, pp. 129–44, doi:<a href=\"https://doi.org/10.1080/00207169008803871\">10.1080/00207169008803871</a>.","short":"H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, J. Feldman, International Journal of Computer Mathematics 34 (1990) 129–144.","ista":"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."},"date_created":"2018-12-11T12:06:46Z","language":[{"iso":"eng"}],"publisher":"Taylor & Francis","scopus_import":"1","date_published":"1990-01-01T00:00:00Z","month":"01","page":"129 - 144","issue":"3-4","publication":"International Journal of Computer Mathematics","status":"public","intvolume":"        34","type":"journal_article","day":"01"},{"year":"1983","doi":"10.1080/00207168308803364","title":"A new approach to rectangle intersections part 1","publication_status":"published","citation":{"ieee":"H. Edelsbrunner, “A new approach to rectangle intersections part 1,” <i>International Journal of Computer Mathematics</i>, vol. 13, no. 3–4. Taylor &#38; Francis, pp. 209–219, 1983.","apa":"Edelsbrunner, H. (1983). A new approach to rectangle intersections part 1. <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/00207168308803364\">https://doi.org/10.1080/00207168308803364</a>","chicago":"Edelsbrunner, Herbert. “A New Approach to Rectangle Intersections Part 1.” <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis, 1983. <a href=\"https://doi.org/10.1080/00207168308803364\">https://doi.org/10.1080/00207168308803364</a>.","ama":"Edelsbrunner H. A new approach to rectangle intersections part 1. <i>International Journal of Computer Mathematics</i>. 1983;13(3-4):209-219. doi:<a href=\"https://doi.org/10.1080/00207168308803364\">10.1080/00207168308803364</a>","mla":"Edelsbrunner, Herbert. “A New Approach to Rectangle Intersections Part 1.” <i>International Journal of Computer Mathematics</i>, vol. 13, no. 3–4, Taylor &#38; Francis, 1983, pp. 209–19, doi:<a href=\"https://doi.org/10.1080/00207168308803364\">10.1080/00207168308803364</a>.","ista":"Edelsbrunner H. 1983. A new approach to rectangle intersections part 1. International Journal of Computer Mathematics. 13(3–4), 209–219.","short":"H. Edelsbrunner, International Journal of Computer Mathematics 13 (1983) 209–219."},"abstract":[{"text":"Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.","lang":"eng"}],"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert"}],"publist_id":"1993","volume":13,"date_updated":"2022-01-25T12:21:18Z","article_processing_charge":"No","_id":"4126","extern":"1","publication_identifier":{"issn":["0020-7160"],"eissn":["1029-0265"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","month":"09","article_type":"original","date_published":"1983-09-01T00:00:00Z","publisher":"Taylor & Francis","scopus_import":"1","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:07:05Z","day":"01","type":"journal_article","intvolume":"        13","status":"public","issue":"3-4","publication":"International Journal of Computer Mathematics","page":"209 - 219"},{"title":"A new approach to rectangle intersections part 2","doi":"10.1080/00207168308803365","year":"1983","abstract":[{"text":"The study begun in Part I is completed by providing an algorithm which reports all intersecting pairs of a set of rectangles in d dimensions. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.","lang":"eng"}],"author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","citation":{"mla":"Edelsbrunner, Herbert. “A New Approach to Rectangle Intersections Part 2.” <i>International Journal of Computer Mathematics</i>, vol. 13, no. 3–4, Taylor &#38; Francis, 1983, pp. 221–29, doi:<a href=\"https://doi.org/10.1080/00207168308803365\">10.1080/00207168308803365</a>.","ama":"Edelsbrunner H. A new approach to rectangle intersections part 2. <i>International Journal of Computer Mathematics</i>. 1983;13(3-4):221-229. doi:<a href=\"https://doi.org/10.1080/00207168308803365\">10.1080/00207168308803365</a>","ista":"Edelsbrunner H. 1983. A new approach to rectangle intersections part 2. International Journal of Computer Mathematics. 13(3–4), 221–229.","short":"H. Edelsbrunner, International Journal of Computer Mathematics 13 (1983) 221–229.","ieee":"H. Edelsbrunner, “A new approach to rectangle intersections part 2,” <i>International Journal of Computer Mathematics</i>, vol. 13, no. 3–4. Taylor &#38; Francis, pp. 221–229, 1983.","apa":"Edelsbrunner, H. (1983). A new approach to rectangle intersections part 2. <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/00207168308803365\">https://doi.org/10.1080/00207168308803365</a>","chicago":"Edelsbrunner, Herbert. “A New Approach to Rectangle Intersections Part 2.” <i>International Journal of Computer Mathematics</i>. Taylor &#38; Francis, 1983. <a href=\"https://doi.org/10.1080/00207168308803365\">https://doi.org/10.1080/00207168308803365</a>."},"_id":"4127","publication_identifier":{"issn":["0020-7160"],"eissn":["1029-0265"]},"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","publist_id":"1994","volume":13,"date_updated":"2022-01-25T12:33:10Z","article_processing_charge":"No","publisher":"Taylor & Francis","scopus_import":"1","language":[{"iso":"eng"}],"month":"09","date_published":"1983-09-01T00:00:00Z","article_type":"original","date_created":"2018-12-11T12:07:06Z","intvolume":"        13","status":"public","day":"01","type":"journal_article","issue":"3-4","publication":"International Journal of Computer Mathematics","page":"221 - 229"}]