--- res: bibo_abstract: - "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@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Bernard foaf_name: Chazelle, Bernard foaf_surname: Chazelle - 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 bibo_doi: 10.1007/BF02187875 bibo_issue: '1' bibo_volume: 2 dct_date: 1987^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0179-5376 - http://id.crossref.org/issn/1432-0444 dct_language: eng dct_publisher: Springer@ dct_title: Linear space data structures for two types of range search@ ...