Generation of constrained network Voronoi diagram using linear tessellation and expansion method

As a well-known geometric construction, Voronoi diagrams play an important role in applications of location-based services, such as accessibility analysis and nearest route detection. Because the movement in urban areas is constrained by the street network under certain transformation conditions, it is necessary to construct a new type of Voronoi diagram based on the network path distance rather than the conventional Euclidean distance. This study presents a constrained network Voronoi diagram using stream flowing ideas. A new distance, the “lixel distance”, is defined to measure the travel cost by subdividing the edge into small linear segments constrained by travel speed and other traffic conditions. Based on the stream of flowing ideas, the algorithm lets all studied source streams spread over the network paths until meeting other streams or arriving at the end of an edge. This process is similar to the expansion operation in the raster geo-processing of Euclidean space. By comparison with the previous approaches in a static environment, this algorithm can be applied to accurately estimate service areas for facilities in real time and to easily add constraints of movement and traffic, such as one-way traffic and restricted street access. The experiment on real POI data to find the service areas in Guangzhou city, China shows that the proposed algorithm is efficient and effective.