---
_id: '4070'
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.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mark
  full_name: Overmars, Mark
  last_name: Overmars
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
- first_name: Irith
  full_name: Hartman, Irith
  last_name: Hartman
- first_name: Jack
  full_name: Feldman, Jack
  last_name: Feldman
citation:
  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>
  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>.
  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.
  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.
  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.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-21T13:19:52Z
day: '01'
doi: 10.1080/00207169008803871
extern: '1'
intvolume: '        34'
issue: 3-4
language:
- iso: eng
main_file_link:
- url: https://www.tandfonline.com/doi/abs/10.1080/00207169008803871
month: '01'
oa_version: None
page: 129 - 144
publication: International Journal of Computer Mathematics
publication_identifier:
  eissn:
  - 1029-0265
  issn:
  - 0020-7160
publication_status: published
publisher: Taylor & Francis
publist_id: '2051'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ranking intervals under visibility constraints
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 34
year: '1990'
...
---
_id: '4126'
abstract:
- lang: eng
  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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  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>
  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>.
  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.
  ista: Edelsbrunner H. 1983. A new approach to rectangle intersections part 1. International
    Journal of Computer Mathematics. 13(3–4), 209–219.
  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>.
  short: H. Edelsbrunner, International Journal of Computer Mathematics 13 (1983)
    209–219.
date_created: 2018-12-11T12:07:05Z
date_published: 1983-09-01T00:00:00Z
date_updated: 2022-01-25T12:21:18Z
day: '01'
doi: 10.1080/00207168308803364
extern: '1'
intvolume: '        13'
issue: 3-4
language:
- iso: eng
month: '09'
oa_version: None
page: 209 - 219
publication: International Journal of Computer Mathematics
publication_identifier:
  eissn:
  - 1029-0265
  issn:
  - 0020-7160
publication_status: published
publisher: Taylor & Francis
publist_id: '1993'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new approach to rectangle intersections part 1
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1983'
...
---
_id: '4127'
abstract:
- lang: eng
  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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  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>
  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>.
  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.
  ista: Edelsbrunner H. 1983. A new approach to rectangle intersections part 2. International
    Journal of Computer Mathematics. 13(3–4), 221–229.
  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>.
  short: H. Edelsbrunner, International Journal of Computer Mathematics 13 (1983)
    221–229.
date_created: 2018-12-11T12:07:06Z
date_published: 1983-09-01T00:00:00Z
date_updated: 2022-01-25T12:33:10Z
day: '01'
doi: 10.1080/00207168308803365
extern: '1'
intvolume: '        13'
issue: 3-4
language:
- iso: eng
month: '09'
oa_version: None
page: 221 - 229
publication: International Journal of Computer Mathematics
publication_identifier:
  eissn:
  - 1029-0265
  issn:
  - 0020-7160
publication_status: published
publisher: Taylor & Francis
publist_id: '1994'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new approach to rectangle intersections part 2
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1983'
...