**F. Aurenhammer, G. Stoeckl, and E. Welzl**

The post-office problem for point sites in the plane (determine which site
is closest to a later specified query point) is generalized to the situation
when the residence of each site is uncertain and it is described via uniform
distribution within a disk. Two probabilistic concepts of neighborhood, -
expected closest site and probably closest site - are discussed and the
resulting Voronoi diagrams are investigated from a combinatorial and
computational point of view.