Variable-speed City Voronoi Diagram Generated

Considering the shortest time between two points on the L₁-plane, the cityVoronoi diagram is presented. Being an extension of the Voronoi diagram in the metric, it is of more importance. This paper extends the definition of city Voronoi diagram, and presents a new city Voronoi diagram—city Voronoi diagram with a various-speed transportation network. This type of the Voronoi diagram is defined, and its basic properties are investigated. At the same time an approximation algorithm is proposed. This algorithm is based on a method of crystal growth, and it is appropriate for the city Voronoi diagram. Crystal growth is that starting from several different points and each point extends outside all around with the growth method of its own. This proposed algorithm is independent of the number of generators and the number of nodes of the transportation network. It is simple to implement and efficient. And the proposed algorithm acts better especially for constructing this type of city Voronoi diagram with more generators and more complicated transportation network.