max planck institut

informatik

informatik

Max-Planck-Institut
für Informatik

Department 1: Algorithms and
Complexity

Campus E1 4, Room
319

66123 Saarbrücken

Germany

**Email:**
Get my email address via email

**Phone:** +49 681 9325 1019

**Fax:** +49 681 9325 199

- Discrete and Computational Geometry
- Extremal Combinatorics

- Conflict-Free
Coloring for Rectangle Ranges Using O(n
^{0.382}) Colors

with Deepak Ajwani, Khaled Elbassioni and Sathish Govindarajan

Accepted to*Discrete and Computational Geometry* - Faster
Algorithms for Computing Hong's Bound on Absolute
Positiveness

with Kurt Mehlhorn

*Journal of Symbolic Computation, 2010*

- Hitting Simplices with
Points in R
^{3}with Abdul Basit, Nabil Mustafa and Sarfraz Raza

*Discrete and Computational Geometry, 2010* **Improved Results on Geometric Hitting Set Problems**

with Nabil Mustafa

*Discrete and Computational Geometry, 2010***Centerpoints and Tverberg's Technique**

with Abdul Basit, Nabil Mustafa and Sarfraz Raza

*Computational Geometry: Theory and Applications*, 2010**An Optimal Generalization of the Centerpoint Theorem**

*Computational Geometry: Theory and Applications*, 2008**Weak ε-nets have a Basis of size O(1/ε log 1/ε)**

*Computational Geometry: Theory and Applications*, 2008

with Oswin Aichholzer, Franz Aurenhammer , Paola Gonzalez-Nava, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser and Birgit Vogtenhuber**Matching Edges and Faces in Polygonal Partitions**

*Computational Geometry: Theory and Applications*, 2008

*A Theorem of Barany Revisited and Extended*with Nabil Mustafa

*Proc. of the 28th ACM Symposium on Computational Geometry (SoCG)*, 2012, to appear.- Counting
Crossing Free Structures
with Victor Alvarez, Karl Bringmann and Radu Curticapean

*Proc. of the 28th ACM Symposium on Computational Geometry (SoCG)*, 2012, to appear. - Ray-Shooting
Depth:
Computing
Statistical Data Depth of Point Sets in the Plane

*European Symposium on Algorithms (ESA)*, 2011 - Enumerating Minimal Transversals of Geometric
Hypergraphs

*Canadian Conference on Computational Geometry (CCCG)*, 2011 - Improving
the first selection lemma in R
^{3}

*Proc. of the 26th ACM Symposium on Computational Geometry (SoCG)*, 2010. with Nabil Mustafa**PTAS for Geometric Hitting Set Problems via Local Search**(There is an error in the proof of Theorem 1.2. A corrected version is**here)**

*Proc. of the 25th ACM Symposium on Computational Geometry (SoCG)*, 2009.

- On Profit-Maximizing
Pricing for the Highway and Tollbooth Problems

*Proc. of 2nd Symposium**on Algorithmic Game Theory (SAGT)*, 2009.

with Khaled Elbassioni, Rajiv Raman and Rene Sitters**On the approximability of the maximum feasible subsystem problem with 0/1-coefficients**

*ACM-SIAM Symposium on Discrete Algorithms (SODA) 2009*

**New Existence proofs for ε-Nets**

*Proc. of the 24th ACM Symposium on Computational Geometry (SoCG )*, 2008.

**On Computing the Centroid of the Vertices of an Arrangement and Related Problems**

*Workshop on Algorithms and Data Structures (WADS), Halifax, Canada, 2007*

with Deepak Ajwani, Khaled Elbassioni, Sathish Govindarajan**Conflict-Free Coloring for Rectangle Ranges Using O(n**^{0.382+ε}) Colors

*Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, CA, USA, 2007*

**Weak ε-nets have a Basis of size O(1/ε log 1/ε)**

*Proc. of the 23rd ACM Symposium on Computational Geometry (SoCG)*, 2007.

with Nabil Mustafa**An Optimal Generalization of the Centerpoint Theorem**

*Proc. of the 23rd ACM Symposium on Computational Geometry (SoCG)*, 2007.

with Oswin Aichholzer, Franz Aurenhammer , Paola Gonzalez-Nava, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser and Birgit Vogtenhuber**Matching Edges and Faces in Polygonal Partitions**

*Canadian Conference on Computational Geometry 2005*with Raimund Seidel**A Simple and Less Slow Method for Counting Triangulations and for Related Problems**

*European Workshop on Computational Geometry 2004*

*Optimization
Topological
Methods in Geometry*

*February 2011 - present : post doctoral researcher at Kurt Mehlhorn's group at Max-Planck-Institut für Informatik, Germany*

*February 2010 - January 2011: post doctoral researcher Janos Pach's group at*École polytechnique fédérale de Lausanne*, Switzerland*

*April 2009 - January 2010: post doctoral researcher in Kurt Mehlhorn's group at Max-Planck-Institut für Informatik, Germany*

*September 2004 - March 2009:*

Ph. D. student in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany

*April 2003 - July 2004:*

M.Sc. in Computer Science at Universität des Saarlandes and Max-Planck-Institut für Informatik, Germany*August 1997 - May 2001:*

Bachelor of Computer Science at Indian Institute of Technology, Guwahati, India