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
2102958968 2778261679 2949155877 2031212151
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. Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length @math such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold @math . Subsequent authors have reduced their time and space bounds such that, when @math is given at preprocessing time, we need either @math space and optimal @math query time or linear space and @math query time, where @math is the alphabet size. In this paper we give the first linear-space solution with optimal @math query time. For the case when @math is given at query time, we significantly improve previous bounds, achieving either @math space and optimal @math query time or compressed space and @math query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by (2012), who achieved linear space and @math query time even for variable @math . We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest. Given a set S of n sites (points), and a distance measure d , the nearestneighborsearching problem is to build a data structure so that given a query point q , the site nearest to q can be found quickly. This paper gives data structures for this problem when the sites and queries are in a metric space. One data structure, D(S) , uses a divide-and-conquer recursion. The other data structure, M(S,Q) , is somewhat like a skiplist. Both are simple and implementable. The data structures are analyzed when the metric space obeys a certain sphere-packing bound, and when the sites and query points are random and have distributions with an exchangeability property. This property implies, for example, that query point q is a random element of ( S q ) . Under these conditions, the preprocessing and space bounds for the algorithms are close to linear in n . They depend also on the sphere-packing bound, and on the logarithm of the distanceratio ( (S) ) of S , the ratio of the distance between the farthest pair of points in S to the distance between the closest pair. The data structure M(S,Q) requires as input data an additional set Q , taken to be representative of the query points. The resource bounds of M(S,Q) have a dependence on the distance ratio of S ( )Q . While M(S,Q) can return wrong answers, its failure probability can be bounded, and is decreasing in a parameter K . Here K≤ |Q| n is chosen when building M(S,Q) . The expected query time for M(S,Q) is O(Klog n)log ( (S Q) ) , and the resource bounds increase linearly in K . The data structure D(S) has expected O( log n) O(1) query time, for fixed distance ratio. The preprocessing algorithm for M(S,Q) can be used to solve the all nearest neighbor problem for S in O(n(log n) 2 (log ϒ(S)) 2 ) expected time.