Optimal solutions for a class of point retrieval problems

B. Chazelle, H. Edelsbrunner

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in C+q can be retrieved efficiently. If constant time sumces for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and O(k + log n) time for a query with output size k. If C is a disk, the problem becomes the wellknown fixed-radius neighbour problem, to which we thus provide the first known optimal solution.

Original languageEnglish (US)
Pages (from-to)47-56
Number of pages10
JournalJournal of Symbolic Computation
Volume1
Issue number1
DOIs
StatePublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Optimal solutions for a class of point retrieval problems'. Together they form a unique fingerprint.

Cite this