@inproceedings{9ed053cfe917453dbf3af621660fa1e2,

title = "Linear space data structures for two types of range search",

abstract = "This paper investigates the existence of linear space data structures for range searching. We examine the homothetic range search problem, where a set S of n points in the plane is to be preprocessed so that for any triangle T with sides parallel to three fixed directions the points of S that lie in T can be computed efficiently. We also look at domination searching in three dimensions. In this problem, S is a set of n points in E3 and the question is to retrieve all points of S 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 near-optimal in the second.",

author = "B. Chazelle and H. Edelsbrunner",

note = "Funding Information: The first author was supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786. Funding Information: supported in part by NSF; 2nd Annual Symposium on Computational Geometry, SCG 1986 ; Conference date: 02-06-1986 Through 04-06-1986",

year = "1986",

month = aug,

day = "1",

doi = "10.1145/10515.10547",

language = "English (US)",

series = "Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986",

publisher = "Association for Computing Machinery, Inc",

pages = "293--302",

booktitle = "Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986",

}