Streaming complexity of fundamental Geometric Problems

Sandeep Sen
IIT Delhi, and Shiv Nadar University
02.06.2020 14:00 to 16:00
IRB 4105

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