In this talk, we discuss algorithms for some basic geometric problems in the one-pass (insertion only) streaming model. These problems include approximating Klee's measure, Convex hull, fixed dimensional linear programming and densest interval.
For all the problems considered, we present (randomized) lower bounds on space. Most of our lower bounds are in terms of approximating the solution with respect to an error parameter $\epsilon$.
Joint work with Arijit Bishnu, Amit Chakrabarti, Arijit Ghosh, Gopinath Mishra, Subhas Nandy and Sai Praneeth
Sandeep Sen is Director, School of Engineering, Shiv Nadar University, currently on leave from IIT Delhi where he has been a Professor of CSE since 2000. His research interests include randomized algorithms and data structures, geometric algorithms, dynamic graph algorithms and models of computation. He is a Fellow of the Indian National Science Academy and the Indian Academy of Sciences.
Sandeep Sen holds a BTech from IIT Kharagpur, MS from UC Santa Barbara and a PhD from Duke University.