Linear space data structures for two types of range search

B. Chazelle, H. Edelsbrunner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986
PublisherAssociation for Computing Machinery, Inc
Pages293-302
Number of pages10
ISBN (Electronic)0897911946, 9780897911948
DOIs
StatePublished - Aug 1 1986
Externally publishedYes
Event2nd Annual Symposium on Computational Geometry, SCG 1986 - Yorktown Heights, United States
Duration: Jun 2 1986Jun 4 1986

Publication series

NameProceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986

Other

Other2nd Annual Symposium on Computational Geometry, SCG 1986
CountryUnited States
CityYorktown Heights
Period6/2/866/4/86

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Linear space data structures for two types of range search'. Together they form a unique fingerprint.

Cite this