17 citations · 24 across the 7 of their papers we have counts for
11 papers
Geometric Optimization Parameterized by Piercing Complexity
Aritra Banik, Rajiv Raman, Saurabh Ray
Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatne…
W-state graphs: Structure and Algorithms
Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos
We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away phy…
Threshold Rounding for the Standard LP Relaxation of some Geometric Stabbing Problems
Khaled Elbassioni, Saurabh Ray
In the rectangle stabbing problem, we are given a set $\cR$ of axis-aligned rectangles in $\RR^2$, and the objective is to find a minimum-cardinality set of horizontal and/or verti…
Tighter Estimates for epsilon-nets for Disks
Norbert Bus, Shashwat Garg, Nabil H. Mustafa +1
The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set of points, and a set of geometric objects in the…
QPTAS for Geometric Set-Cover Problems via Optimal Separators
Nabil H. Mustafa, Rajiv Raman, Saurabh Ray
Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. the breakthrough of Bansal-Pruhs (FOCS 2010) reduces a wide class of mac…
Counting Triangulations and other Crossing-Free Structures Approximately
Victor Alvarez, Karl Bringmann, Saurabh Ray +1
We consider the problem of counting straight-edge triangulations of a given set of points in the plane. Until very recently it was not known whether the exact number of tri…
Counting Triangulations and other Crossing-free Structures via Onion Layers
Victor Alvarez, Karl Bringmann, Radu Curticapean +1
Let be a set of points in the plane. A crossing-free structure on is a plane graph with vertex set . Examples of crossing-free structures include triangulations of $…
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations
Victor Alvarez, Karl Bringmann, Saurabh Ray
Let be a set of points. In this paper we show two new algorithms, one to compute the number of triangulations of , and one to compute the number of…
On Totally Positive Matrices and Geometric Incidences
Miriam Farber, Saurabh Ray, Shakhar Smorodinsky
A matrix is called totally positive if every minor of it is positive. Such matrices are well studied and have numerous applications in Mathematics and Computer Science. We study ho…
Point Line Cover: The Easy Kernel is Essentially Tight
Stefan Kratsch, Geevarghese Philip, Saurabh Ray
The input to the NP-hard Point Line Cover problem (PLC) consists of a set of points on the plane and a positive integer , and the question is whether there exists a set…
On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
Khaled Elbassioni, Rajiv Raman, Saurabh Ray +1
In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with edges, and a set of customers, each of whom is interested in purchasing a path on the tree. Each custo…