---
_id: '4099'
abstract:
- lang: eng
  text: Let S denote a set of n points in the Euclidean plane. A halfplanar range
    query specifies a halfplane h and requires the determination of the number of
    points in S which are contained in h. A new data structure is described which
    stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1)
    time in the worst case, thus improving the best result known before. The structure
    can be built in O(n log n) time.
acknowledgement: 'We thank W. Bucher for help in the analysis of the time complexity
  of the query algorithm. '
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. Halfplanar range search in linear space and O(n0.695)
    query time. <i>Information Processing Letters</i>. 1986;23(5):289-293. doi:<a
    href="https://doi.org/10.1016/0020-0190(86)90088-8">10.1016/0020-0190(86)90088-8</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). Halfplanar range search in linear
    space and O(n0.695) query time. <i>Information Processing Letters</i>. Elsevier.
    <a href="https://doi.org/10.1016/0020-0190(86)90088-8">https://doi.org/10.1016/0020-0190(86)90088-8</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear
    Space and O(N0.695) Query Time.” <i>Information Processing Letters</i>. Elsevier,
    1986. <a href="https://doi.org/10.1016/0020-0190(86)90088-8">https://doi.org/10.1016/0020-0190(86)90088-8</a>.
  ieee: H. Edelsbrunner and E. Welzl, “Halfplanar range search in linear space and
    O(n0.695) query time,” <i>Information Processing Letters</i>, vol. 23, no. 5.
    Elsevier, pp. 289–293, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and
    O(n0.695) query time. Information Processing Letters. 23(5), 289–293.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space
    and O(N0.695) Query Time.” <i>Information Processing Letters</i>, vol. 23, no.
    5, Elsevier, 1986, pp. 289–93, doi:<a href="https://doi.org/10.1016/0020-0190(86)90088-8">10.1016/0020-0190(86)90088-8</a>.
  short: H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-24T00:00:00Z
date_updated: 2022-02-01T14:17:10Z
day: '24'
doi: 10.1016/0020-0190(86)90088-8
extern: '1'
intvolume: '        23'
issue: '5'
language:
- iso: eng
month: '11'
oa_version: None
page: 289 - 293
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2021'
quality_controlled: '1'
status: public
title: Halfplanar range search in linear space and O(n0.695) query time
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 23
year: '1986'
...