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].
A Semi-Separated Pair Decomposition (SSPD), with parameter s>1, of a set S@?R^d is a set (A"i,B"i) of pairs of subsets of S such that for each i, there are balls D"A"""i and D"B"""i containing A"i and B"i respectively such that d(D"A"""i,D"B"""i)>=s@?min(radius(D"A"""i),radius(D"B"""i)), and for any two points p,q@?S there is a unique index i such that p@?A"i and q@?B"i or vice versa. In this paper, we use the SSPD to obtain the following results: First, we consider the construction of geometric t-spanners in the context of imprecise points and we prove that any set S@?R^d of n imprecise points, modeled as pairwise disjoint balls, admits a t-spanner with O(nlogn (t-1)^d) edges that can be computed in O(nlogn (t-1)^d) time. If all balls have the same radius, the number of edges reduces to O(n (t-1)^d). Secondly, for a set of n points in the plane, we design a query data structure for half-plane closest-pair queries that can be built in O(n^2log^2n) time using O(nlogn) space and answers a query in O(n^1^ ^2^+^@e) time, for any @e>0. By reducing the preprocessing time to O(n^1^+^@e) and using O(nlog^2n) space, the query can be answered in O(n^3^ ^4^+^@e) time. Moreover, we improve the preprocessing time of an existing axis-parallel rectangle closest-pair query data structure from quadratic to near-linear. Finally, we revisit some previously studied problems, namely spanners for complete k-partite graphs and low-diameter spanners, and show how to use the SSPD to obtain simple algorithms for these problems.   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. An important query for spatial database research is to find the closest pair of objects in a given space. Existing work assumes two objects of the closest pair come from two different data sets indexed by R-trees. The closest pair in the whole space will be found via an optimzed R-tree join technique. However, this technique doesn’t perform well when the two data sets are identical. And it doesn’t work when the search range is some area other than the whole space. In this paper, we address the closest pair problem within the same data set. Further more, we propose a practical extension to the closest pair problem to involve a query range. The problem now becomes finding the closest pair of objects among those inside a given range. After extending the existing techniques to solve the new problem, we proposed two index structures based on augmenting the R-tree and we also give algorithms for maintaining these structrures. Experimental results show that our structures are more robust than earlier approaches. We consider variations of the standard orthogonal range searching motivated by applications in database querying and VLSI layout processing. In a generic instance of such a problem, called a range-aggregate query problem we wish to preprocess a set S of geometric objects such that given a query orthogonal range q, a certain intersection or proximity query on the objects of S intersected by q can be answered efficiently. Although range-aggregate queries have been widely investigated in the past for aggregation functions like average, count, min, max, sum etc. we consider aggregation operations involving geometric intersection searching problems in this paper. Efficient solutions are provided for point enclosure queries for d ≥ 1, 1-d interval intersection, 2-d orthogonal segment intersection and interval rectangle hyper-rectangle enclosure queries in this framework.  Abstract A comprehensive overview is given of algorithms and data structures for proximity problems on point sets in ℝ D . In particular, the closest pair problem, the exact and approximate post-office problem, and the problem of constructing spanners are discussed in detail. A fundamental and well-studied problem in computational geometry is range searching, where the goal is to preprocess a set, S, of geometric objects (e.g., points in the plane) so that the subset S^'@?S that is contained in a query range (e.g., an axes-parallel rectangle) can be reported efficiently. However, in many situations, what is of interest is to generate a more informative ''summary'' of the output, obtained by applying a suitable aggregation function on S^'. Examples of such aggregation functions include count, sum, min, max, mean, median, mode, and top-k that are usually computed on a set of weights defined suitably on the objects. Such range-aggregate query problems have been the subject of much recent research in both the database and the computational geometry communities. In this paper, we further generalize this line of work by considering aggregation functions on point-sets that measure the extent or ''spread'' of the objects in the retrieved set S^'. The functions considered here include closest pair, diameter, and width. The challenge here is that these aggregation functions (unlike, say, count) are not efficiently decomposable in the sense that the answer to S^' cannot be inferred easily from answers to subsets that induce a partition of S^'. Nevertheless, we have been able to obtain space- and query-time-efficient solutions to several such problems including: closest pair queries with axes-parallel rectangles on point sets in the plane and on random point-sets in R^d (d>=2), closest pair queries with disks on random point-sets in the plane, diameter queries on point-sets in the plane, and guaranteed-quality approximations for diameter and width queries in the plane. Our results are based on a combination of geometric techniques, including multilevel range trees, Voronoi Diagrams, Euclidean Minimum Spanning Trees, sparse representations of candidate outputs, and proofs of (expected) upper bounds on the sizes of such representations. In the range closest pair problem, we want to construct a data structure storing a set @math of @math points in the plane, such that for any axes-parallel query rectangle @math , the closest pair in the set @math can be reported. The currently best result for this problem is by (SoCG 2018). Their data structure has size @math and query time @math . We show that a data structure of size @math can be constructed in @math time, such that queries can be answered in @math time, where @math is the aspect ratio of @math . Thus, for fat query rectangles, the query time is @math . This result is obtained by reducing the range closest pair problem to standard range searching problems on the points of @math . 