17 citations · 24 across the 7 of their papers we have counts for
7 papers · 1 filter
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…
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…