Data structures for range-aggregate extent queries (Q390147)

A very important problem in computational geometry is range searching, where the goal is to preprocess a set, \(S\), of geometric objects so that the subset \(S' \subseteq S\) that is contained in a query range can be reported efficiently. However, in general, one is interested in generating 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. In this paper, the authors generalize this line of work by aggregating functions on point-sets that measure the extent or spread of the objects in the retrieved set \(S'\). The functions considered include closest pair, diameter, and width. These aggregation functions 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, the authors 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 \({\mathbb R}^d\), 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. The results in this paper 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 upper bounds on the sizes of such representations.