We consider a range-search variant of the closest-pair problem. Let @math be a fixed shape in the plane. We are interested in storing a given set of @math points in the plane in some data structure such that for any specified translate of @math , the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when @math is a polygon (possibly with holes) and when @math is a general convex body whose boundary is smooth. When @math is a polygon, we present a data structure using @math space and @math query time, which is asymptotically optimal. When @math is a general convex body with a smooth boundary, we give a near-optimal data structure using @math space and @math query time. Our results settle some open questions posed by [SoCG 2018].
Given a dataset @math of points in @math , the range closest-pair (RCP) problem aims to preprocess @math into a data structure such that when a query range @math is specified, the closest-pair in @math can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.