Given a set of generators, the geodesic Voronoi diagram (GVD) defines how the base
surface is decomposed into separate regions such that each generator dominates a region
in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector
point of the GVD is determined by two adjacent generators while each branching point of the
GVD is given by at least three generators. When there are sufficiently many generators,
straight-line distance serves as an effective alternative of geodesic distance for computing …