---
_id: '4105'
abstract:
- lang: eng
  text: "A finite set of lines partitions the Euclidean plane into a cell complex.
    Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions $d$-dimensional
    Euclidean space. An algorithm is presented that constructs a representation for
    the cell complex defined by $n$ hyperplanes in optimal $O(n^d )$ time in $d$ dimensions.
    It relies on a combinatorial result that is of interest in its own right. The
    algorithm is shown to lead to new methods for computing $\\lambda $-matrices,
    constructing all higher-order Voronoi diagrams, halfspatial range estimation,
    degeneracy testing, and finding minimum measure simplices. In all five applications,
    the new algorithms are asymptotically faster than previous results, and in several
    cases are the only known methods that generalize to arbitrary dimensions. The
    algorithm also implies an upper bound of $2^{cn^d } $, $c$ a positive constant,
    for the number of combinatorially distinct arrangements of $n$ hyperplanes in
    $E^d $.\r\n© 1986 Society for Industrial and Applied Mathematics"
acknowledgement: "We thank Emmerich Welzl for discussions on Theorem 2.7. We also
  thank Friedrich Huber for implementing the \r\nconstruction of arrangements in arbitrary
  dimensions, and Gerd Stoeckl for implementing the algorithms presented in §§\r\n4.1
  and 4.3. The third author wishes to thank Jack Edmonds for the many enlightening
  discussions.\r\n"
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
- first_name: Joseph
  full_name: O'Rourke, Joseph
  last_name: O'Rourke
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
citation:
  ama: Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and
    hyperplanes with applications. <i>SIAM Journal on Computing</i>. 1986;15(2):341-363.
    doi:<a href="https://doi.org/10.1137/0215024">10.1137/0215024</a>
  apa: Edelsbrunner, H., O’Rourke, J., &#38; Seidel, R. (1986). Constructing arrangements
    of lines and hyperplanes with applications. <i>SIAM Journal on Computing</i>.
    SIAM. <a href="https://doi.org/10.1137/0215024">https://doi.org/10.1137/0215024</a>
  chicago: Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing
    Arrangements of Lines and Hyperplanes with Applications.” <i>SIAM Journal on Computing</i>.
    SIAM, 1986. <a href="https://doi.org/10.1137/0215024">https://doi.org/10.1137/0215024</a>.
  ieee: H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of
    lines and hyperplanes with applications,” <i>SIAM Journal on Computing</i>, vol.
    15, no. 2. SIAM, pp. 341–363, 1986.
  ista: Edelsbrunner H, O’Rourke J, Seidel R. 1986. Constructing arrangements of lines
    and hyperplanes with applications. SIAM Journal on Computing. 15(2), 341–363.
  mla: Edelsbrunner, Herbert, et al. “Constructing Arrangements of Lines and Hyperplanes
    with Applications.” <i>SIAM Journal on Computing</i>, vol. 15, no. 2, SIAM, 1986,
    pp. 341–63, doi:<a href="https://doi.org/10.1137/0215024">10.1137/0215024</a>.
  short: H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986)
    341–363.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T11:03:07Z
day: '01'
doi: 10.1137/0215024
extern: '1'
intvolume: '        15'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 341 - 363
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2017'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constructing arrangements of lines and hyperplanes with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...
---
_id: '4110'
abstract:
- lang: eng
  text: For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection,
    called the arrangement of H. We define the notion of a belt in $A(H)$, which is
    bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing
    belts. All this is motivated by applications to a host of seemingly unrelated
    problems including a type of range search and finding the minimum area triangle
    with the vertices taken from some finite set of points.
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
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements
    with applications. <i>SIAM Journal on Computing</i>. 1986;15(1):271-284. doi:<a
    href="https://doi.org/10.1137/0215019">10.1137/0215019</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). Constructing belts in two-dimensional
    arrangements with applications. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/0215019">https://doi.org/10.1137/0215019</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
    Arrangements with Applications.” <i>SIAM Journal on Computing</i>. SIAM, 1986.
    <a href="https://doi.org/10.1137/0215019">https://doi.org/10.1137/0215019</a>.
  ieee: H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements
    with applications,” <i>SIAM Journal on Computing</i>, vol. 15, no. 1. SIAM, pp.
    271–284, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements
    with applications. SIAM Journal on Computing. 15(1), 271–284.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
    Arrangements with Applications.” <i>SIAM Journal on Computing</i>, vol. 15, no.
    1, SIAM, 1986, pp. 271–84, doi:<a href="https://doi.org/10.1137/0215019">10.1137/0215019</a>.
  short: H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.
date_created: 2018-12-11T12:07:00Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T09:34:20Z
day: '01'
doi: 10.1137/0215019
extern: '1'
intvolume: '        15'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 271 - 284
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2014'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constructing belts in two-dimensional arrangements with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...