# An Algorithm to Generate a Weighted Network Voronoi Diagram Based on Improved PCNN
## 1 Introduction  
As an excellent tool for spatial analysis and spatial optimization, the Voronoi diagram has been applied in various fields [1, 2, 3]. Originally, it was defined through a set of \(n\) points \(P=\{P_{1},\,\ldots,P_{n}\}\) (termed generator points or generators) on the plane, where the Euclidean distance between an arbitrary point \(p_{i}\) and a generator point \(p\) is \(d\) (\(p,p_{i}\)) [4, 5, 6]. In these terms, the ordinary planar Voronoi diagram is defined as a set of polygons, \(\text{Vor}=\{\text{Vor}_{1},\,\ldots,\,\text{Vor}_{n}\}\), where the polygon \(\text{Vor}_{i}\) is given by  
\[Vor_{i}=\{p|d(p,p_{i})\leq d(p,p_{j}),j\
eq i,j=1,\ldots,n\} \tag{1}\]  
An example of a Voronoi diagram is illustrated in Figure 1. It can be seen that the distance between points is computed by Euclidean distance in the planar Voronoi diagram.  
However, in the real-world cases, the accessibility between points that stand for geographic objects are generally constrained by road networks [7, 8]. The Euclidean-distance-based Voronoi diagram is less proper as a subdivision of network space. In the literature, although there are many phenomena that occur on a network or alongside a network, they are often analyzed based on the planar Voronoi diagram. Therefore, it is significant to propose methods to build applicable Voronoi diagrams in the network space.  
The network Voronoi diagram replaces the plane with network space (such as a road network) compared with the planar Voronoi diagram. Correspondingly, distances defined on a network (such as the shortest path distance between two points) [6, 9] are applied instead of the Euclidean distance, which can be defined as:\[\text{Vor}=\{\text{Vor}_{1},\,\text{Vor}_{2},\,\ldots,\,\text{Vor}_{n}\} \tag{2}\]  
where \(\text{Vor}_{i}=\{P\,|\,d(p,\,p_{i})\leq d(p,\,p_{i})\}\); \(d(p,\,p_{i})\) is the distance between an arbitrary point \(p_{i}\) and a generator point \(p\) in the network [10; 11; 12]. It is a better choice for spatial division and analysis [6], and it has been widely utilized. [PERSON] et al. (2021) found an optimal partition that minimizes the overall delivery time of all trucks based on the weighted road network Voronoi diagram [13]. [PERSON] et al. (2017) proposed and evaluated a searching scheme for a biochromatic reverse k-nearest neighbor with a network Voronoi diagram [14]. [PERSON] et al. (2011) studied the maximal covering spatial optimization based on network Voronoi diagram [15]. [PERSON] et al. (2014) proposed the method for logistics routing optimization based on a network Voronoi diagram [16]. [PERSON] (1994) presented a method for market area delimitation [17].  
In this study, we propose an algorithm for dynamically constructing network Voronoi diagrams. The approach attempts to take advantage of the properties of concurrency and auto-wave distribution of the PCNN. The basic idea is that auto-waves are generated from initial neurons and transmit along the shortest path between neurons at a calculated speed until all the neurons are fired and the transmitting of auto-wave stops.  
The organization of this paper is as follows. Section 2 introduces the improved PCNN. In Section 3, the procedures of generating the weighted network Voronoi diagram on the basis of the improved PCNN are described. Experiments are illustrated and discussed in Section 4. Finally, conclusions and future works are presented in Section 5.