A zone diagram is a certain geometric object which a variation on the notion of Voronoi diagram. It was introduced by Tetsuo Asano, Jiří Matoušek, and Takeshi Tokuyama in 2007.[1]

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

edit

Consider a group of   different points   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   the set   of all points in the plane whose distance to the given site   is not greater to their distance to any other site  . The collection   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   is defined a little bit differently: instead of associating it the set of all points whose distance to   is not greater than their distance to the other sites, we associate to   the set   of all points in the plane whose distance to   is not greater than their distance to any other region. Formally,

 .

Here   denotes the euclidean distance between the points   and   and   is the distance between the point   and the set  . In addition,   since we consider the plane. The tuple   is the zone diagram associated with the sites.

The problem with this definition is that it seems circular: in order to know   we should know   for each index   but each such   is defined in terms of  . On a second thought, we see that actually the tuple   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

edit

In some settings, such as the one described above, a zone diagram can be interpreted as a certain equilibrium between mutually hostile kingdoms,.[1][2] In a discrete setting it can be interpreted as a stable configuration in a certain combinatorial game.[2]

Formal definition

edit

Let   be a metric space and let   be a set of at least 2 elements (indices), possibly infinite. Given a tuple   of nonempty subsets of  , called the sites, a zone diagram with respect to this tuple is a tuple   of subsets of   such that for all   the following equation is satisfied:

 

Zone diagram as a fixed point

edit

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   let   be the set of all nonempty subsets of  . Let

 

and let   be the function defined by  , where   and

 

Then   is a zone diagram if and only if it is a fixed point of Dom, that is,  . 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

edit

Following the pioneering work of Asano et al.[1] (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:

  • 2 sites (existence): there exists at least one zone diagram for any pair of arbitrary sites in any metric space. In fact, this existence result holds in any m-space[2] (a generalization of metric space in which, for instance, the distance function may be negative and may not satisfy the triangle inequality).
  • More than 2 sites (existence): there exists a zone diagram of finitely many compact and disjoint sites contained in the interior of a compact and convex subset of a uniformly convex space. This result actually holds in a more general setting.[3]
  • More than 2 sites (existence and uniqueness): there exists a unique zone diagram with respect to any collection (possibly infinite) of closed and positively separated sites in any finite-dimensional euclidean space. Positively separated means that there exists a positive lower bound on the distance between any two sites. A similar result was formulated for the case in which the normed space is finite-dimensional and is both uniformly convex and uniformly smooth.[4]
  • non-uniqueness: simple examples are known even for the case of two point sites,.[2][4]

Computation

edit

More information is needed.

edit

In addition to Voronoi diagrams, zone diagrams are closely related to other geometric objects such as double zone diagrams,[2] trisectors,[5] k-sectors,[6] mollified zone diagrams[7] and as a result may be used for solving problems related to robot motion and VLSI design,.[5][6]

References

edit
  1. ^ a b c Asano, Tetsuo; Matoušek, Jiří; Tokuyama, Takeshi (2007). "Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge". SIAM Journal on Computing. 37 (4): 1182–1198. doi:10.1137/06067095X. Preliminary version in Proc. SODA 2007, pp. 756-765.
  2. ^ a b c d e Reem, Daniel; Reich, Simeon (2009). "Zone and double zone diagrams in abstract spaces". Colloquium Mathematicum. 115: 129–145. arXiv:0708.2668. doi:10.4064/cm115-1-11.
  3. ^ Kopecká, Eva; Reem, Daniel; Reich, Simeon (2012). "Zone diagrams in compact subsets of uniformly convex normed spaces". Israel Journal of Mathematics. 188: 1–23. arXiv:1002.3583. doi:10.1007/s11856-011-0094-5. Preliminary versions in Proc. CCCG 2010, pp. 17-20.
  4. ^ a b Kawamura, Akitoshi; Matoušek, Jiří; Tokuyama, Takeshi (2012). "Zone diagrams in Euclidean spaces and in other normed spaces". Mathematische Annalen. 354: 1201–1221. arXiv:0912.3016. doi:10.1007/s00208-011-0761-1. Preliminary version in Proc. SoCG 2010, pp. 216-221.
  5. ^ a b Asano, Tetsuo; Matoušek, Jiří; Tokuyama, Takeshi (2007). "The distance trisector curve". Advances in Mathematics. 212: 338–360. doi:10.1016/j.aim.2006.10.006. Preliminary version in Proc. STOC 2006, pp. 336--343.
  6. ^ a b Imai, Keiko; Kawamura, Akitoshi; Matoušek, Jiří; Tokuyama, Takeshi; Reem, Daniel; Tokuyama, Takeshi (2010). "Distance k-sectors exist". Computational Geometry. 43 (9): 713–720. arXiv:0912.4164. doi:10.1016/j.comgeo.2010.05.001. Preliminary versions in Proc. SoCG 2010, pp. 210–215.
  7. ^ Biasi, Sergio C.; Kalantari, Bahman; Kalantari, Iraj (2011). "Mollified Zone Diagrams and Their Computation". Transactions on Computational Science XIV. Lecture Notes in Computer Science. Vol. 6970. pp. 31–59. doi:10.1007/978-3-642-25249-5_2. ISBN 978-3-642-25248-8. Preliminary version in Proc. ISVD 2010, pp. 171--180