Geometric algorithms for Proximity and Uncertainty

Dr. Nirman Kumar
University of California, Santa Barbara


Abstract

The modern age is undoubtedly the age of data. Technological inventions have made the process of sensing, acquiring, and storing data easy to an extent that we have "too much of data". Unfortunately, not all of this data is precise -- data imprecision and uncertainty is prevalent with huge amounts of data, geometric or otherwise. In this talk I will focus on two main problems on geometric computing for such big data in low dimensions: (i) A fast data-structure for computing an approximate k-th nearest neighbor in the form of an Approximate Voronoi diagram - the complexity of the data-structure gets better as k increases, and, (ii) for uncertainty modeled in the existential model, i.e., each point p_i in question is known to be active or only exists with a certain probability \alpha_i, and has an associated non-negative value v_i, we show how to compute expected range-max for rectangular query ranges in sublinear time with sub-quadratic storage for any constant dimension. I will also discuss directions for future research.