It is probably some basic statistics question, but...
Informally 1: How to choose "criteria", such that it will guarantee that error decision probability is less than "epsilon", and maximize probability of correct decision ? ("Criteria", "probabilities" will be explained below).
Informally 2 consider some points A_i in R^n. Task - for given point "x", find nearest point A_i. It is exactly the same determine to what Voronoi cell point "x" belongs to. Now imagine that point "x" is exactly on the same distance between several points A_i, then the answer to the question is not unique. Now let us add some randomness in this setup (see details below) so we should expect that if point "x" is "near" the edge of the Voronoi cell, our decision to say that the closest point is say A_1 will not be reliable. So I need to "decrease" Voronoi cells such that I can guarantee reliability is bigger than (1-epsilon).
My question will be - what is the shape of these "epsilon-soften" Voronoi cells ? (Of course, I will need to specify "probabilities" - see below).
Setup for formal question Consider some points S_i in R^n. Consider some R^n-valued random vector "N" (say Gaussian) (N - is "noise"). Define R=S+N, where S is random variable which uniformly takes values S_i (S-"sent signal", "R"-"received signal").
Question How to define subsets D_i in R^n, such that:
1) Probability that "R" belongs to D_i, under condition that $S\ne A_i$ is less than epsilon (small probability of incorrect signal detection)
2) For all other choices of subsets D_i satisfying (1), the probability of "R" belongs to D_i, under condition that $S=A_i$ is maximal possible over all choices of subsets D_i satisfying (1).
D_i - are our "soft" Voronoi cells.
The informal sense is the following - D_i are some neigbourhouds of points A_i, which are small enough to guarantee (1) (incorrect decision has small probability), but the biggest among all subsets satisfying (1) (we want to maximize the probability of correct decision).
Remark In R^1 this is standard simple statistics knowledge, but the question seems to be non-trivial even in R^2.
SubQuestion 1 What are the references ?
SubQuestion 2 Is there some simple knowledge that everybody must understand before start thinking on the question ?
SubQuestion 3 Is the question difficult ? Or there is some simple solution ? (Yes/No)
SubQuestion 4 Is it true that D_i cutted by hyperplanes (similar to Voronoi cells) ? (Yes/No)
SubQuestion 5 If problem is difficult in general, then is there some approximate solution (algorithm), which satisfy (1), and gives non-bad maximization in (2) ?
