A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions

In this work we revisit the maximum range sum (MaxRS) problem which is well studied by the database and the computational geometry communities. The input is a set P of n weighted points in R d and a geometric range Q (typically either an axis-aligned d -box or a d -ball). The goal is to design a fast algorithm to place Q in R d so that the total weight of the points of P inside Q is maximized. We consider three natural variations of the MaxRS problem: In the dynamic MaxRS problem, points are inserted and deleted, and the goal is to efficiently update the placement of a d -ball. In R d we present a randomized (1/2 - ε)-approximation algorithm with update time O ε (log n). The approximation factor holds with high probability. To the best of our knowledge, this problem was not studied before in the literature. In the batched MaxRS problem in R 1 , along with the points in P we are given m intervals of different lengths. The goal is to solve the MaxRS problem for each interval. We establish a conditional lower bound of Ω(mn) time for this problem, assuming the hardness of (min,+)-convolution problem. Interestingly, this implies that the trivial upper bound of O(mn log n) for batched MaxRS in R 2 is almost-tight. A similar lower bound is established for a related problem of batched smallest k -enclosing interval. In the colored MaxRS problem in R d , each point in P is assigned a color from 1,2,...,m and the goal is to find the placement of a d -ball Q that maximizes the number of uniquely colored points in P ∩ Q. Prior work on this problem was limited to axis-aligned rectangle Q in R 2 . We obtain two new results for d -balls. The first result is a randomized (1/2 - ε)-approximation algorithm with running time O ε (n log n). Interestingly, the exponential dependence of log n on d is avoided in the running time. The second result improves upon the first result in R 2 by providing a (1-ε)-approximation algorithm with expected running time O_ε(n log n). The approximation factor holds with high probability for both results. Our algorithms are obtained via two general techniques which we believe will be useful for solving other variants of MaxRS. The first technique provides a (1/2 - ε)-approximation guarantee. The analysis relies on a volume argument involving d -balls and a randomized game. The second technique provides a (1-ε)-approximation guarantee and works in two phases. In the first phase, we design an exact output-sensitive algorithm, and in the second phase, we speed up the exact algorithm by random sampling on colors.