@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 = "Publisher Copyright: {\textcopyright} 1986 ACM.; 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",
}