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

 

Research Interests

Teaching

Past Courses

  • Design and Analysis of Algorithms (August - December, 2011)
  • Combinatorial Geometry (January - May, 2011)
  • Design and Analysis of Algorithms (August - December, 2010)
  • Combinatorial Geometry (January - May, 2010)
  • Design and Analysis of Algorithms (August - December, 2009) (co-taught with Kavitha)
  • Combinatorial Geometry (January - May, 2009)
  • Design and Analysis of Algorithms (August - December, 2008)
  • Combinatorial Geometry (January - May, 2008)

 

Publications

Conferences

On Computing Locally Gabriel Graphs, Submitted
(with Abhijeet Khopkar)

On the Erdos-Szekeres n-interior point problem,
(with Subramanya Bharadwaj and Karmveer Sharma)
Accepted. 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 Rectangle Ranges using $O(n^{.382+\epsilon})$ colors,
(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).

Journals

On Locally Gabriel Graphs, Submitted.

Small Strong Epsilon Nets, Submitted.
(with Pradeesha Ashok, Umair Azmi)

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

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 

Ph.D Dissertation

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