Fulltext

Zone diagrams in Euclidean spaces and in other normed spaces

Kawamura, Akitoshi ; Matoušek, Jiří ; Tokuyama, Takeshi

In: Mathematische Annalen, 2012, vol. 354, no. 4, p. 1201-1221

Add to personal list
    Title
    • Zone diagrams in Euclidean spaces and in other normed spaces
    Author
    • Kawamura, Akitoshi. Department of Computer Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-8656, Tokyo, Japan
    • Matoušek, Jiří. Department of Applied Mathematics, Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic
    • Tokuyama, Takeshi. Graduate School of Information Sciences, Tohoku University, Aramaki Aza Aoba, Aoba-ku, 980-8579, Sendai, Japan
    Document Type
    • Postprint
    Classification
    • Mathematics
    OAI-PMH Identifier
    • oai:doc.rero.ch:321779
    Summary
    Zone diagrams are a variation on the classical concept of Voronoi diagrams. 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, Matoušek, and Tokuyama proved the existence and uniqueness of a zone diagram for point sites in the 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 etal. 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