4 papers · 1 filter
A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
Rachana Gusain, Saladi Rahul, Aditya Subramanian
We revisit the maximum range sum (MaxRS) problem: given a set of weighted points in and a range (typically axis-aligned -box or -ball), the goal is…
On Approximation Schemes for Stabbing Rectilinear Polygons
Arindam Khan, Aditya Subramanian, Tobias Widmann +1
We study the problem of stabbing rectilinear polygons, where we are given rectilinear polygons in the plane that we want to stab, i.e., we want to select horizontal line segmen…
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Arindam Khan, Aditya Lonkar, Saladi Rahul +2
Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric version…
A PTAS for the horizontal rectangle stabbing problem
Arindam Khan, Aditya Subramanian, Andreas Wiese
We study rectangle stabbing problems in which we are given axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each g…