The post office problem for fuzzy point sets (Q4035741)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 176569
Language Label Description Also known as
default for all languages
No label defined
    English
    The post office problem for fuzzy point sets
    scientific article; zbMATH DE number 176569

      Statements

      0 references
      0 references
      0 references
      18 May 1993
      0 references
      computational geometry
      0 references
      proximity
      0 references
      probabilistic
      0 references
      fuzzy point set
      0 references
      query answering
      0 references
      post office problem
      0 references
      data structure
      0 references
      Voronoi diagrams
      0 references
      The post office problem for fuzzy point sets (English)
      0 references
      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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references