Sathish Govindarajan
Associate Professor
CSA Department
Indian Institute of Science, Bangalore.

 

Research Interests



Teaching

Past Courses

Publications

Journals

On a problem of Danzer and Grunbaum, Submitted.
(with Subramanya Bharadwaj and Chintan Rao)

Selection Lemmas for various geometric objects, Submitted.
(with Pradeesha Ashok and Ninad Rajgopal)
Arxiv version

On Strong Centerpoints
(with Pradeesha Ashok)
Information Processing Letters, 2015
Arxiv version

On Locally Gabriel Geometric Graphs
(with Abhijit Khopkar)
Graphs and Combinatorics, 2015
Arxiv version

Hardness results on computing Locally Gabriel Graphs
(with Abhijit Khopkar)
International Journal of Computational Geometry and Applications, 2014
Arxiv version

Small Strong Epsilon Nets
(with Pradeesha Ashok, Umair Azmi)
Computational geometry: Theory and Applications. 2014
Arxiv version

Two player game variant of the Erdos-Szekeres problem
(with Kolipaka Parikshit)
Discrete Mathematics and Theoretical Computer Science, 2013
Arxiv version

On the Erdos-Szekeres n-interior point problem
(with Subramanya Bharadwaj and Karmveer Sharma)
European Journal of Combinatorics, 2014.

Conflict-free coloring for Rectangle Ranges using $O(n^{.382+\epsilon})$ colors,
(with Deepak Ajwani, Khaled Elbassioni, and Saurabh Ray)
Discrete and Computational Geometry, 2012.

A Scalable Algorithm for Dispersing Population,
(with Pankaj K. Agarwal, James Clark and Mike Dietze)
Journal of Intelligent Information System, Special Issue on Ecoinformatics, 2007.

I/O Efficient Well-Separated Pair Decomposition and its Applications.,
(with Tamas Lukovzski,Anil Maheshwari and Norbert Zeh)
 Algorithmica. 45(4):585-614, 2006 

Conferences

On the d-runaway rectangle escape problem,
(with Aniket Basu Roy, Neeldhara Misra and Shreyas Shetty)
Canadian Conference of Computational Geometry (CCCG '14).

Vertex cover gets faster and harder on low degree graphs,
(with Akanksha Agrawal and Neeldhara Mishra)
Conference of Computing and Combinatorics (COCOON '14).

Hitting and piercing rectangles induced by a point set,
(with Ninad Rajgopal, Pradeesha Ashok, Abhijit Khopkar and Neeldhara Mishra)
Conference of Computing and Combinatorics (COCOON '13).

Piercing (pseudo)lines and boxes,
(with Subramanya Bharadwaj, Pradeesha Ashok and Chintan Rao)
Canadian Conference of Computational Geometry (CCCG '12).

On Computing Optimal Locally Gabriel Graphs,
(with Abhijeet Khopkar)
Canadian Conference of Computational Geometry (CCCG '12).

On the Erdos-Szekeres n-interior point problem
(with Subramanya Bharadwaj and Karmveer Sharma)
European Conference on Combinatorics, Graph Theory and Applications, 2011.

Small Strong Epsilon Nets,
(with Pradeesha Ashok, Janardhan Kulkarni)
Canadian Conference of Computational Geometry (CCCG '10).

New Epsilon Net Constructions,
(with Janardhan Kulkarni)
Canadian Conference of Computational Geometry (CCCG '10).

Conflict-free coloring for Rectangles,
(with Deepak Ajwani, Khaled Elbassioni, and Saurabh Ray)
ACM Symposium of Parallelism and Algorithms in Architecture (SPAA ’07).

A Scalable Simulator for Forest Dynamics,
(with Pankaj K. Agarwal, James Clark and Mike Dietze)
Proc. of the 20th Annual ACM Symposium on Computational Geometry (SoCG '04).

CRB-Tree: An Efficient Indexing Scheme for Range Aggregate Queries,
(with Pankaj Agarwal and Lars Arge)
Proc. of the 9th International Conference on Database Theory (ICDT '03).

Range Searching in Categorical Data : Colored Range Searching on Grid,
(with Pankaj Agarwal and S. Muthukrishnan)
Proc. of the 10th European Symposium on Algorithms (ESA '02). 

I/O Efficient Well-Separated Pair Decomposition and its Applications,
(with Tamas Lukovzski,Anil Maheshwari and Norbert Zeh)
Proc. of the 8th Annual European Symposium on Algorithms (ESA '00).


Ph.D Dissertation

Sathish Govindarajan. Spatial Data Structures and Algorithms for Large Scale Applications. Ph.d Thesis. Duke University, Decemeber 2004.