Premium
The graph Voronoi diagram with applications
Author(s) -
Erwig Martin
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200010)36:3<156::aid-net2>3.0.co;2-l
Subject(s) - voronoi diagram , weighted voronoi diagram , power diagram , computation , graph , computer science , centroidal voronoi tessellation , bowyer–watson algorithm , graph theory , algorithm , theoretical computer science , mathematics , combinatorics , geometry
The Voronoi diagram is a famous structure of computational geometry. We show that there is a straightforward equivalent in graph theory which can be efficiently computed. In particular, we give two algorithms for the computation of graph Voronoi diagrams, prove a lower bound on the problem, and identify cases where the algorithms presented are optimal. The space requirement of a graph Voronoi diagram is modest, since it needs no more space than does the graph itself. The investigation of graph Voronoi diagrams is motivated by many applications and problems on networks that can be easily solved with their help. This includes the computation of nearest facilities, all nearest neighbors and closest pairs, some kind of collision free moving, and anticenters and closest points. © 2000 John Wiley & Sons, Inc.