Zone Diagrams in Euclidean Spaces and in Other Normed Spaces

Details Zone Diagrams in Euclidean Spaces and in Other Normed Spaces Zone Diagrams in Euclidean Spaces and in Other Normed Spaces

2009-12-15

arxiv.org/abs/0912.3016v1

Computer Science

Computational Geometry

Title page + 16 pages, 20 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Zone Diagrams in Euclidean Spaces and in Other Normed Spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Zone Diagrams in Euclidean Spaces and in Other Normed Spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Zone Diagrams in Euclidean Spaces and in Other Normed Spaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-48264