Before revision:  We show how to preprocess G in \tilde O(nb^2) time \tilde  so that one can compute any additively weighted Voronoi diagram for these sites in \tilde O(b) time.
After revision:  We show how to preprocess G in \tilde O(nb^2) time \tilde O notation hides polylogarithmic factors.) so that one can compute any additively weighted Voronoi diagram for these sites in \tilde O(b) time.