Zone and double zone diagrams in abstract spaces

Daniel Reem¹ ; Simeon Reich¹

¹ Department of Mathematics The Technion – Israel Institute of Technology 32000 Haifa, Israel

Colloquium Mathematicum, Tome 115 (2009) no. 1, pp. 129-145

Résumé

A zone diagram of order $n$ is a relatively new concept which was first defined and studied by T. Asano, J. Matou\v{s}ek and T. Tokuyama. It can be interpreted as a state of equilibrium between $n$ mutually hostile kingdoms. Formally, it is a fixed point of a certain mapping. These authors considered the Euclidean plane with finitely many singleton-sites and proved the existence and uniqueness of zone diagrams there. In the present paper we generalize this concept in various ways. We consider general sites in $m$-spaces (a simple generalization of metric spaces) and prove several existence and (non)uniqueness results in this setting. In contrast with previous works, our (rather simple) proofs are based on purely order-theoretic arguments. Many explicit examples are given, and some of them illustrate new phenomena which occur in the general case. We also re-interpret zone diagrams as a stable configuration in a certain combinatorial game, and provide an algorithm for finding this configuration in a particular case.

Détail

DOI : 10.4064/cm115-1-11

Keywords: zone diagram order relatively concept which first defined studied asano matou tokuyama interpreted state equilibrium between mutually hostile kingdoms formally fixed point certain mapping these authors considered euclidean plane finitely many singleton sites proved existence uniqueness zone diagrams there present paper generalize concept various ways consider general sites m spaces simple generalization metric spaces prove several existence uniqueness results setting contrast previous works rather simple proofs based purely order theoretic arguments many explicit examples given illustrate phenomena which occur general re interpret zone diagrams stable configuration certain combinatorial game provide algorithm finding configuration particular