Streaming complexity of fundamental Geometric Problems
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