---
_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'
...