## Abstract

The range closest-pair (RCP) problem, as a range-search version of the classical closest-pair problem, aims to store a dataset of points in some data structure such that whenever a query range Q is given, the closest-pair inside Q can be reported efficiently. This paper studies an approximate version of the RCP problem in which the answer pair is allowed to be “approximately” contained in the query range. A general reduction from the approximate RCP problem to the range-minimum and range-reporting problems is given, which works for a general class of query spaces. The reduction is applied to obtain efficient approximate RCP data structures for disk queries in ℝ^{2} and ball queries in higher dimensions. Finally, the paper also shows that for orthogonal queries, the approximate RCP problem is (asymptotically) at least as hard as the orthogonal range-minimum problem.

Original language | English (US) |
---|---|

Pages | 282-287 |

Number of pages | 6 |

State | Published - Jan 1 2018 |

Event | 30th Canadian Conference on Computational Geometry, CCCG 2018 - Winnipeg, Canada Duration: Aug 8 2018 → Aug 10 2018 |

### Conference

Conference | 30th Canadian Conference on Computational Geometry, CCCG 2018 |
---|---|

Country | Canada |

City | Winnipeg |

Period | 8/8/18 → 8/10/18 |