@article{4099,
  abstract     = {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.},
  author       = {Edelsbrunner, Herbert and Welzl, Emo},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {5},
  pages        = {289 -- 293},
  publisher    = {Elsevier},
  title        = {{Halfplanar range search in linear space and O(n0.695) query time}},
  doi          = {10.1016/0020-0190(86)90088-8},
  volume       = {23},
  year         = {1986},
}