Sharath Raghvendra PhotographSharath Raghvendra

Department of Computer Science
Virginia Tech

Email: sharathr at



About Me

I am an Assistant Professor in the Department of Computer Science at Virginia Tech. Prior to joining Virginia Tech, I spent two years as a postdoc in the Computer Science and Management Science and Engineering departments at Stanford working with Prof. Leo Guibas and Prof. Ashish Goel. I completed my Ph.D. from the Department of Computer Science at Duke University where I worked with Prof. Pankaj Agarwal. I received my B. Tech (Hons) (Computer Science) from IIIT, Hyderabad.


Research Interests

My research interests is in the domain of computational geometry. In particular, I am interested in design of algorithms for large-scale, unstructured and potentially high-dimensional geometric data.

I am also interested in design of approximation algorithms that solve optimization problems over large scale inputs. In my Ph.D. thesis titled Geometric Approximation Algorithms - A Summary Based Approach , I designed efficient approximation algorithms for fundamental geometric optimization problems using a summary based approach, i.e., quickly compute a compact representation (or summary) of the input and extract an approximately optimal solution from this summary by a relatively slower algorithm. My dissertation won the Duke Computer Science Outstanding Ph.D. dissertation for 2012.




"The Geometry Behind Logistics Approximation Algorithms for RealTime Delivery" (NSF CRII), $175,000, Feb’15- Jan’17



CS4104: Data and Algorithm Analysis (Fall’14)

CS6104: Online Algorithms (Spring’15)




Connectivity in Random Forests and Credit Networks
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang
SODA 2015.

Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs
Pankaj K. Agarwal, R. Sharathkumar
STOC 2014.

Approximate Cech Complex in Low and High Dimensions
Michael Kerber, R. Sharathkumar
ISAAC 2013.

A Sub-Quadratic Algorithm For Bipartite Matching of Planar Points with Bounded Integer Coordinates
R. Sharathkumar.
SOCG 2013

A Near-Linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
R. Sharathkumar, Pankaj K. Agarwal.
STOC 2012 (To Appear in Journal of the ACM)

Algorithms for Transportation Problem in Geometric Settings
R. Sharathkumar, Pankaj K. Agarwal.
SODA 2012

Streaming Algorithms for Extent Problems in High Dimensions
Pankaj K. Agarwal, R. Sharathkumar
SODA 2010 (Appears in Algorithmica)

Approximate Euclidean Shortest-paths amid Convex Obstacles
Pankaj K. Agarwal, R. Sharathkumar, Hai Yu.
SODA 2009

On approximate geodesic-distance queries amid deforming point clouds
Pankaj K. Agarwal, Alon Efrat, R. Sharathkumar, Hai Yu.
WAFR 2008

Range Aggregate Proximity Queries
R. Sharathkumar, Prosenjit Gupta.
Technical Report, 2007.

Range Aggregate Proximity Detection for Design Rule Checking in VLSI layouts
R. Sharathkumar, Prosenjit Gupta.
CCCG, 2006.