Japanese

Zone Diagrams in Euclidean Spaces and in Other Normed Spaces

Akitoshi Kawamura, Jiří Matoušek and Takeshi Tokuyama. Zone diagrams in Euclidean spaces and in other normed spaces. Mathematische Annalen 354(4), 1201–1221, December 2012. DOI = 10.1007/s00208-011-0761-1

Akitoshi Kawamura, Jiří Matoušek and Takeshi Tokuyama. Zone diagrams in Euclidean spaces and in other normed spaces. In the Proceedings of the 26th Annual ACM Symposium on Computational Geometry (SoCG 2010), pages 216–221, Snowbird, Utah, USA, June 2010. DOI = 10.1145/1810959.1810997

Akitoshi Kawamura, Jiří Matoušek and Takeshi Tokuyama. Zone diagrams in Euclidean spaces and in other normed spaces. IEICE Technical Committee on Theoretical Foundations of Computing, Fukuoka, Japan, January 25, 2010. IEICE Technical Report, vol. 109, no. 391, COMP2009-42, pp. 23–28. In Japanese.

Abstract

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 simpler than Asano et al.'s. 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.

Key words
Knaster–Tarski fixed point theorem, zone diagrams