The post office problem for fuzzy point sets

From MaRDI portal





The well-known post office problem is as follows. Preprocess \(n\) points (sites) in the plane into a data structure which enables quick answering for queries ``For a query point, find the closest site. The classic approach to the problem is via Voronoi diagrams. The paper generalizes the problem into the probabilistic setting, where the position of each site is described by a uniform distribution within a disk. Two measures of closeness are considered for queries: 1. Find a cite with maximal probability of being closest to the query point; 2. Find a cite with minimal expected distance from the query point. The paper investigates the resulting (generalizations of) Voronoi diagrams. It turns out that in the second case the Voronoi diagram may be constructed in randomized \(O(n\log n)\) time. The first case is much more complicated and deserves further investigation. Some other kinds of fuzzy Voronoi diagrams are also briefly discussed. For the entire collection see [Zbl 0753.00016].











This page was built for publication: The post office problem for fuzzy point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035741)