The post-office problem for fuzzy point sets

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

Abstract:

The post-office problem for $n$ 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.

Reference: F. Aurenhammer, G. Stoeckl, and E. Welzl. The post-office problem for fuzzy point sets. In Proc. $7^{th}$ Workshop on Computational Geometry CG '91, Lecture Notes in Computer Science, volume 553, pages 1-11, Bern, Switzerland, 1991. Springer Verlag. [Report B 91-07, FU Berlin, Germany, 1991].