Zone diagrams in Euclidean spaces and in other normed spaces

DOI10.1007/S00208-011-0761-1zbMATH Open1263.52005arXiv0912.3016OpenAlexW2570492632WikidataQ56590867 ScholiaQ56590867MaRDI QIDQ695282FDOQ695282

Authors: Akitoshi Kawamura, Takeshi Tokuyama, Jiří Matoušek 

Publication date: 20 December 2012

Published in: Mathematische Annalen (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/0912.3016

Recommendations

• Zone diagrams in Euclidean spaces and in other normed spaces
• Zone diagrams in compact subsets of uniformly convex normed spaces
• Zone and double zone diagrams in abstract spaces
• Zone diagrams: existence, uniqueness and algorithmic challenge
• Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge

zbMATH Keywords

existenceuniquenessnormed spaceVoronoi diagramsEuclidean spacepoint siteszone diagram

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Normed linear spaces and Banach spaces; Banach lattices (46B99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A lattice-theoretical fixpoint theorem and its applications
• Zone and double zone diagrams in abstract spaces
• Zone diagrams in compact subsets of uniformly convex normed spaces
• Mollified zone diagrams and their computation
• Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge
• Distance trisector of a segment and a point
• Zone diagrams in Euclidean spaces and in other normed spaces
• The distance trisector curve

Cited In (9)

• Zone diagrams in compact subsets of uniformly convex normed spaces
• Zone diagrams in Euclidean spaces and in other normed spaces
• Mollified zone diagrams and their computation
• Fixed points of polarity type operators
• On the computation of zone and double zone diagrams
• On the existence of a neutral region. II: The implicit relation case
• Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge
• Zone and double zone diagrams in abstract spaces
• Zone diagrams: existence, uniqueness and algorithmic challenge

This page was built for publication: Zone diagrams in Euclidean spaces and in other normed spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q695282)