Zone diagram

A zone diagram is a certain geometric object which a variation on the notion of Voronoi diagram. It was introduced by Tetsuo Asano, Jiri Matousek, and Takeshi Tokuyama in 2007.
Formally, it is a fixed point of a certain function. Its existence or uniqueness are not clear in advance and have been established only in specific cases. Its computation is not obvious either.
A particular but informative case.
Consider a group of formula_1 different points formula_2 in the Euclidean plane. Each point is called a site. When we speak about the Voronoi diagram induced by these sites, we associate to the site formula_3 the set formula_4 of all points in the plane whose distance to the given site formula_3 is not greater to their distance to any other site formula_6. The collection formula_7 of these regions is the Voronoi diagram associated with these sites, and it induces a decomposition of the plane into regions: the Voronoi regions (Voronoi cells).
In a zone diagram the region associated with the site formula_8 is defined a little bit differently: instead of associating it the set of all points whose distance to formula_8 is not greater than their distance to the other sites, we associate to formula_8 the set formula_11 of all points in the plane whose distance to formula_8 is not greater than their distance to any other region. Formally,
Here formula_14 denotes the euclidean distance between the points formula_15 and formula_16 and formula_17 is the distance between the point formula_18 and the set formula_19. In addition, formula_20 since we consider the plane. The tuple formula_7 is the zone diagram associated with the sites.
The problem with this definition is that it seems circular: in order to know formula_11 we should know formula_23 for each index formula_24 but each such formula_23 is defined in terms of formula_4. On a second thought, we see that actually the tuple formula_7 is a solution of the following system of equations:
Rigorously, a zone diagram is any solution of this system, if such a solution exists. This definition can be extended without essentially any change to higher dimensions, to sites which are not necessarily points, to infinitely many sites, etc.
Interpretation.
In some settings, such as the one described above, a zone diagram can be interpreted as a certain equilibrium between mutually hostile kingdoms. In a discrete setting it can be interpreted as a stable configuration in a certain combinatorial game.
Formal definition.
Let formula_29 be a metric space and let formula_30 be a set of at least 2 elements (indices), possibly infinite. Given a tuple formula_31 of nonempty subsets of formula_32, called the sites, a zone diagram with respect to this tuple is a tuple formula_33 of subsets of formula_32 such that for all formula_35 the following equation is satisfied:
Zone diagram as a fixed point.
The system of equations which defines the zone diagram can be represented as a fixed point of a function defined on a product space. Indeed, for each index formula_37 let formula_38 be the set of all nonempty subsets of formula_39.
Let
and let formula_41 be the function defined by formula_42, where formula_43 and
Then formula_45 is a zone diagram if and only if it is a fixed point of Dom, that is, formula_46. Viewing zone diagrams as fixed points is useful since in some settings known tools or approaches from fixed point theory can be used for investigating them and
deriving relevant properties (existence, etc.).
Existence and uniqueness.
Following the pioneering work of Asano et al. (existence and uniqueness of the zone diagram in the euclidean plane with respect to finitely many point sites), several existence or existence and uniqueness results have been published. As of 2012, the most general results which have been published are:
Computation.
More information is needed.
Related objects and possible applications.
In addition to Voronoi diagrams, zone diagrams are closely related to other geometric objects such as double zone diagrams, trisectors, k-sectors, mollified zone diagrams and as a result may be used for solving problems related to robot motion and VLSI design.