Optimal solutions for a class of point retrieval problems

Bernard Chazelle, H. Edelsbrunner

Research output: Contribution to journalArticle

5 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 - Jan 1 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