Multidimensional Bucketing
Luc Devroye · Birkhäuser Boston eBooks · 1986
Several algorithms in computer science operate on points in R d by first storing the points in equal-sized cells, and then traveling from cell to cell, to obtain some solution. Often these algorithms have good expected time behavior when the points are sufficiently smoothly distributed over R d . This will be illustrated here by exhibiting necessary and sufficient conditions on the distribution of the points for linear expected time behavior.