8 citations · 17 across the 11 of their papers we have counts for
12 papers
Minimum Membership Geometric Set Cover in the Continuous Setting
Sathish Govindarajan, Mayuresh Patle, Siddhartha Sarkar
We study the minimum membership geometric set cover, i.e., MMGSC problem [SoCG, 2023] in the continuous setting. In this problem, the input consists of a set of points in $…
Improved Algorithms for Minimum-Membership Geometric Set Cover
Sathish Govindarajan, Siddhartha Sarkar
Bandyapadhyay et al. introduced the generalized minimum-membership geometric set cover (GMMGSC) problem [SoCG, 2023], which is defined as follows. We are given two sets and $P'…
The Runaway Rectangle Escape Problem
Aniket Basu Roy, Anil Maheshwari, Sathish Govindarajan +3
Motivated by the applications of routing in PCB buses, the Rectangle Escape Problem was recently introduced and studied. In this problem, we are given a set of rectangles $\mathcal…
A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
Sathish Govindarajan, Gabriel Nivasch
Let be a convex curve in the plane (say, the unit circle), and let be a family of planar convex bodies, such that every two of them meet at a point of . Then $\…
Vertex Cover Gets Faster and Harder on Low Degree Graphs
Akanksha Agrawal, Sathish Govindarajan, Neeldhara Misra
The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set pr…
Selection Lemmas for various geometric objects
Pradeesha Ashok, Ninad Rajgopal, Sathish Govindarajan
Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delauna…
Geometric graphs on convex point sets
Abhijeet Khopkar, Sathish Govindrajan
In this note, we introduce a family of bipartite graphs called path restricted ordered bipartite graphs and present it as an abstract generalization of some well known geometric gr…
On Strong Centerpoints
Pradeesha Ashok, Sathish Govindarajan
Let be a set of points in and be a family of geometric objects. We call a point a strong centerpoint of w.r.t if $x…
Small Strong Epsilon Nets
Pradeesha Ashok, Umair Azmi, Sathish Govindarajan
Let P be a set of n points in . A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than points of P.…
Two player game variant of the Erdos-Szekeres problem
Parikshit Kolipaka, Sathish Govindarajan
The classical Erdos-Szekeres theorem states that a convex -gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic boun…
On Locally Gabriel Geometric Graphs
Sathish Govindarajan, Abhijeet Khopkar
Let be a set of points in the plane. A geometric graph on is said to be {\it locally Gabriel} if for every edge in , the disk with and as diamete…
On Computing Optimal Locally Gabriel Graphs
Abhijeet Khopkar, Sathish Govindarajan
Delaunay and Gabriel graphs are widely studied geometric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as \emph{Locall…