Linear space data structures for two types of range search

Bernard Chazelle, Herbert Edelsbrunner

Research output: Contribution to journalArticle

24 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 nearly optimal in the second.

Original languageEnglish (US)
Pages (from-to)113-126
Number of pages14
JournalDiscrete & Computational Geometry
Volume2
Issue number1
DOIs
StatePublished - Dec 1 1987

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and 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