--- _id: '4100' abstract: - lang: eng text: "This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.\r\n" acknowledgement: This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925. article_processing_charge: No article_type: original author: - first_name: Bernard full_name: Chazelle, Bernard last_name: Chazelle - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 citation: ama: Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search. Discrete & Computational Geometry. 1987;2(1):113-126. doi:10.1007/BF02187875 apa: Chazelle, B., & Edelsbrunner, H. (1987). Linear space data structures for two types of range search. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187875 chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” Discrete & Computational Geometry. Springer, 1987. https://doi.org/10.1007/BF02187875. ieee: B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types of range search,” Discrete & Computational Geometry, vol. 2, no. 1. Springer, pp. 113–126, 1987. ista: Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types of range search. Discrete & Computational Geometry. 2(1), 113–126. mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” Discrete & Computational Geometry, vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:10.1007/BF02187875. short: B. Chazelle, H. Edelsbrunner, Discrete & Computational Geometry 2 (1987) 113–126. date_created: 2018-12-11T12:06:56Z date_published: 1987-01-01T00:00:00Z date_updated: 2022-02-03T11:07:26Z day: '01' doi: 10.1007/BF02187875 extern: '1' intvolume: ' 2' issue: '1' language: - iso: eng month: '01' oa_version: None page: 113 - 126 publication: Discrete & Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer publist_id: '2022' quality_controlled: '1' scopus_import: '1' status: public title: Linear space data structures for two types of range search type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 2 year: '1987' ...