---
_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'
...