Halfplanar range search in linear space and O(n0.695) query time Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Welzl, Emo 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. Elsevier 1986 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4099 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/0020-0190(86)90088-8 info:eu-repo/semantics/altIdentifier/issn/0020-0190 info:eu-repo/semantics/altIdentifier/e-issn/1872-6119 info:eu-repo/semantics/closedAccess