Homepage

Sathish Govindarajan

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 309
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Email:Get my email address via email
Phone: +49 681 9325 109
Fax: +49 681 9325 199

Research Interests

Combinatorial geometry
Spatial data structures
Computational geometry
I/O efficient algorithms

Teaching

· Combinatorial Geometry, Summer Semester 05/06 (with Nabil Mustafa)

Publications

Journals

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

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

A Scalable Algorithm for Computing Light,
(with Pankaj K. Agarwal, James Clark, Sukhendu Chakraborty, Mike Dietze and Mike Wolosin)
(in prep.)

Refereed Conferences

Conflict-free coloring for Rectangle Ranges using $O(n^{.382+\epsilon})$ colors,
(with Deepak Ajwani, Khaled Elbassioni, and Saurabh Ray)
Accepted. 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).

Recent Works

Improved Bounds on Edge Complexity of Local Gabriel Graphs. Manuscript, April 2007

Ph.D Dissertation

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

Recent Positions

December 2004 - July 2005:

Post-doctrate at Computer Science department, Duke University, Durham, USA.