Skip to main content

Generalized network Voronoi diagrams: Concepts, computational methods, and applications

Buy Article:

$63.00 plus tax (Refund Policy)


In the real world, there are many phenomena that occur on a network or alongside a network; for example, traffic accidents on highways and retail stores along streets in an urbanized area. In the literature, these phenomena are analysed under the assumption that distance is measured with Euclidean distance on a plane. This paper first examines this assumption and shows an empirical finding that Euclidean distance is significantly different from the shortest path distance in an urbanized area if the distance is less than 500 m. This implies that service areas in urbanized areas cannot be well represented by Voronoi diagrams defined on a plane with Euclidean distance, termed generalized planar Voronoi diagrams. To overcome this limitation, second, this paper formulates six types of Voronoi diagrams defined on a network, termed generalized network Voronoi diagrams, whose generators are given by points, sets of points, lines and polygons embedded in a network, and whose distances are given by inward/outward distances, and additively/multiplicatively weighted shortest path distances. Third, in comparison with the generalized planar Voronoi diagrams, the paper empirically shows that the generalized network Voronoi diagrams can more precisely represent the service areas in urbanized areas than the corresponding planar Voronoi diagrams. Fourth, because the computational methods for constructing the generalized planar Voronoi diagrams in the literature cannot be applied to constructing the generalized network Voronoi diagrams, the paper provides newly developed efficient algorithms using the 'extended' shortest path trees. Last, the paper develops user-friendly tools (that are included in SANET, a toolbox for spatial analysis on a network) for executing these computational methods in a GIS environment.

Keywords: Directed distance; Farthest point; Network; Shortest path distance; Voronoi diagram; Weighted distance; kth nearest point

Document Type: Research Article


Affiliations: 1: Center for Spatial Information Science, University of Tokyo, c/o Department of Urban Engineering, Bunkyo-ku, Tokyo 113-8656, Japan 2: Application Technology Development, Research and Development Center, Pasco Corporation, Tokyo, 153-0043, Japan 3: Department of Management Science, Tokyo University of Science, Tokyo, 102-0073, Japan 4: Department of Information Systems and Mathematical Sciences, Nanzan University, Seto, 489-0863, Japan

Publication date: 2008-01-01

More about this publication?
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more