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
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
0.8307265043258667
0 references
0.8114312887191772
0 references
0.8021523356437683
0 references
0.7850596904754639
0 references
0.7608990669250488
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