Abstract: As an important geometrical construction obtaining the facility distribution characteristics in geographical space, Voronoi diagram can be constructed differently based on the different distance concept. According to the factor that the service function and interrelation of urban feasilities is carried out on the network path distance, neither than conventional Euclidean distance, this study prsented a raster extension algorithm to build Voronoi diagram in network space, aiming at establishing the network Voronoi diagram model. First the edges of graph structure are subdivided into small linear elements, and we call this procedure as network rasterisation. Then the algorithm introduces the water flow extension idea which lets streams spread on the network paths until meeting the other streams or arriving at the end of edge, with treating the event sources as the headwaters, raster unit length as expanded step length. The algorithm can add constraints of network graph structure, for example, one-way traffic, node restrictive connection. The large-scale actual data experiment for generating the POIs’ service areas in the “Digital City” shows that the proposed algorithm is efficient.

Key words: network Voronoi diagram, spatial tessellation, network analysis, spatial analysis