---
res:
  bibo_abstract:
  - "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@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Herbert
      foaf_name: Edelsbrunner, Herbert
      foaf_surname: Edelsbrunner
      foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9823-6833
  - foaf_Person:
      foaf_givenName: Joseph
      foaf_name: O'Rourke, Joseph
      foaf_surname: O'Rourke
  - foaf_Person:
      foaf_givenName: Raimund
      foaf_name: Seidel, Raimund
      foaf_surname: Seidel
  bibo_doi: 10.1137/0215024
  bibo_issue: '2'
  bibo_volume: 15
  dct_date: 1986^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0097-5397
  - http://id.crossref.org/issn/1095-7111
  dct_language: eng
  dct_publisher: SIAM@
  dct_title: Constructing arrangements of lines and hyperplanes with applications@
...