2009/12/15 by Akitoshi Kawamura, Jiřı́ Matoušek, Jiří Matoušek +1 · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Point processes and geometric inequalities #cs.CG #math.MG
paper · pdf · doi:10.1007/s00208-011-0761-1
published as Mathematische Annalen 354(4):1201-1221, 2012 · Title page + 16 pages, 20 figures
arxiv created 2009/12/15 · crossref issued 2011/11/17 · crossref published 2011/11/17 · crossref published-online 2011/11/17 · openalex publication_date 2011/11/17 · crossref created 2011/11/17 · crossref published-print 2012/12/01 · arxiv updated 2013/05/03 · crossref deposited 2019/06/19 · crossref indexed 2025/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in the competition. Formally it is defined as a fixed point of a certain "dominance" map. Asano, Matousek, and Tokuyama proved the existence and uniqueness of a zone diagram for point sites in Euclidean plane, and Reem and Reich showed existence for two arbitrary sites in an arbitrary metric space. We establish existence and uniqueness for n disjoint compact sites in a Euclidean space of arbitrary (finite) dimension, and more generally, in a finite-dimensional normed space with a smooth and rotund norm. The proof is considerably simpler than that of Asano et al. We also provide an example of non-uniqueness for a norm that is rotund but not smooth. Finally, we prove existence and uniqueness for two point sites in the plane with a smooth (but not necessarily rotund) norm.