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].
We investigate a new variant of the RCP problem in which the query ranges are translates of a fixed shape @math . In the first half of the paper, we assume @math is a fixed polygon (possibly with holes), and give an RCP data structure for @math -translation queries using @math space and @math query time, which is asymptotically optimal. In the second half of the paper, we assume @math is a general convex body with a smooth boundary, and give a near-optimal RCP data structure for @math -translation queries using @math space and @math query time. The @math above hides constants depending on @math . Our results settle some open questions posed in @cite_6 , e.g., the RCP problem with fixed-radius disc queries, etc. In order to design these data structures, we make nontrivial geometric observations and exploit the properties of the problem itself (i.e., we are searching for the in a ). Many of our intermediate results are of independent interest and can probably be applied to other related problems. We describe our key ideas and techniques in after establishing relevant notations in .
@cite_6
2778261679
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.