### 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 language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 12th Colloquium |

Editors | Wilfried Brauer |

Publisher | Springer Verlag |

Pages | 80-89 |

Number of pages | 10 |

ISBN (Print) | 9783540156505 |

DOIs | |

State | Published - Jan 1 1985 |

Externally published | Yes |

Event | 12th International Colloquium on Automata, Languages and Programming, ALP 1985 - Nafplion, Greece Duration: Jul 15 1985 → Jul 19 1985 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 194 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Colloquium on Automata, Languages and Programming, ALP 1985 |
---|---|

Country | Greece |

City | Nafplion |

Period | 7/15/85 → 7/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