{"ID":2868855,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16008","arxiv_id":"2509.16008","title":"A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions","abstract":"We revisit the maximum range sum (MaxRS) problem: given a set $P$ of $n$ weighted points in $\\mathbb{R}^d$ and a range $Q$ (typically axis-aligned $d$-box or $d$-ball), the goal is to place $Q$ to maximize the total weight of points in $P\\cap Q$. We study three natural variations: (1) Dynamic MaxRS: The goal is to update the placement of a $d$-ball under point insertions and deletions. We give a randomized $(\\frac{1}{2}-ε)$-approximation with update time $O_ε(\\log n)$. The approximation factor holds with high probability. To the best of our knowledge, this is the first result on dynamic MaxRS. (2) Batched MaxRS: In $\\mathbb{R}^1$, along with $P$ we are given $m$ intervals of varying lengths. We prove a conditional lower bound of $Ω(mn)$ time (via conjectured $(\\min,+)$-convolution hardness), showing the trivial $O(mn\\log n)$ upper bound in $\\mathbb{R}^2$ is essentially tight. We also establish a similar bound for a related problem of batched smallest $k$-enclosing interval. (3) Colored MaxRS: Each point has a color from $[m]$, and the goal is to place $Q$ to maximize the number of uniquely colored points in $P\\cap Q$. Prior work only considered axis-aligned rectangles in $\\mathbb{R}^2$. For $d$-balls, we give: (a) a randomized $(\\frac{1}{2}-ε)$-approximation in $O_ε(n\\log n)$ time (avoiding exponential dependence on $d$), and (b) in $\\mathbb{R}^2$, a $(1-ε)$-approximation in expected $O_ε(n\\log n)$ time. Both approximations hold with high probability. Our algorithms rely on two techniques of broader interest. The first yields $(\\frac{1}{2}-ε)$-approximations via a volume argument on $d$-balls and a randomized game. The second achieves $(1-ε)$-approximations through an exact output-sensitive algorithm, which we speed up by random sampling on colors.","short_abstract":"We revisit the maximum range sum (MaxRS) problem: given a set $P$ of $n$ weighted points in $\\mathbb{R}^d$ and a range $Q$ (typically axis-aligned $d$-box or $d$-ball), the goal is to place $Q$ to maximize the total weight of points in $P\\cap Q$. We study three natural variations: (1) Dynamic MaxRS: The goal is to upda...","url_abs":"https://arxiv.org/abs/2509.16008","url_pdf":"https://arxiv.org/pdf/2509.16008v1","authors":"[\"Rachana Gusain\",\"Saladi Rahul\",\"Aditya Subramanian\"]","published":"2025-09-19T14:21:39Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}