Optimal solutions for a class of point retrieval problems

Bernard Chazelle, Herbert Edelsbrunner

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

1 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 suffices 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 well-known fized radius neighbor problem, to which we thus provide the first known optimal solution.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 12th Colloquium
EditorsWilfried Brauer
PublisherSpringer Verlag
Pages80-89
Number of pages10
ISBN (Print)9783540156505
DOIs
StatePublished - Jan 1 1985
Externally publishedYes
Event12th International Colloquium on Automata, Languages and Programming, ALP 1985 - Nafplion, Greece
Duration: Jul 15 1985Jul 19 1985

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume194 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Colloquium on Automata, Languages and Programming, ALP 1985
CountryGreece
CityNafplion
Period7/15/857/19/85

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Chazelle, B., & Edelsbrunner, H. (1985). Optimal solutions for a class of point retrieval problems. In W. Brauer (Ed.), Automata, Languages and Programming - 12th Colloquium (pp. 80-89). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 194 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0015733