Alon Hovav, Hebrew University of Jerusalem

Abstract

We present a refined construction of emph{hierarchical probabilistic partitions} with novel properties, substantially stronger than previously known. Our construction provides a family of hierarchical partitions enabling fast dynamic programming algorithms, by guaranteeing that given a sparse set of balls, emph{each cell} of the partition intersects only a small number of balls. The number of balls intersecting a cell is bounded solely as a function of the padding parameter of the partition (which is bounded in particular by the doubling dimension). This is in contrast to the standard guarantee for probabilistic partitions which holds only in expectation. In addition, each cell has a significantly smaller description than in previous constructions.    

[Video]