Zone Diagrams: Existence, Uniqueness and Algorithmic Challenge

Abstract

A zone diagram is a new variation of the classical notion of Voronoi diagram. Given n point sites in the plane, each site is assigned a region consisting of all points that are closer to the site than to all regions of the other site.

We prove existence and uniqueness of the zone diagram, as well as convergence of a natural algorithm computing it.

Keywords

• Diagrams
• Existence
• Uniqueness
• Algorithmic
• Challenge