Next Talk

Abstract

In range counting problems we are given a set of objects, and the goal is to preprocess them, so that given any query range, the number of objects that fall into that range is computed efficiently. For example, the objects are points corresponding to the coordinates of several cities, and we would like to compute how many cities lie within a certain region. In many cases, it is too expensive to process the entire set of objects, which raises the necessity to resort to approximate range counting. Motivated by this problem, relative approximations have become a central tool Computational Geometry. In fact, they were introduced by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, and Srinivasan in the theory of Machine Learning. Informally, a relative approximation is a sample of the input objects that guarantees a bounded relative error for any given range when comparing its exact count (that is, with respect to the entire set of objects) to its approximate count (that is, confined to the sample). In this talk I will discuss the properties of relative approximations and their relation to the so-called "Epsilon-nets". I will also present improved upper bounds for the size of relative approximations, which eventually yields better performance for approximate range counting. Our approach is probabilistic, where we apply the constructive version of the general Local Lemma of Lovasz. Last but not least, I will present a few applications to Sensor Networking and Machine Learning.