2-Point site Voronoi diagrams Original Research Article

In this paper, we define a new type of a planar distance function from a point to a pair of points. We focus on a few such distance functions, analyze the structure and complexity of the corresponding nearest- and furthest-neighbor Voronoi diagrams (in which every region is defined by a pair of point sites), and show how to compute the diagrams efficiently.