The weighted farthest color Voronoi diagram on trees and graphs

摘要

Let n point sites be situated on the vertices or edges of a geometric graph G over e edges. Each site can be assigned a multiplicative weight and a color. We discuss the complexity and provide efficient algorithms for the construction of the Voronoi diagram in which each point of G belongs to the region of that site which is the closest of the furthest color. Special algorithms are presented for the cases when all colors are identical, when all weights are identical, or when G is a tree.