Let $G$ be a graph with (positively) weighted edges. I want to define the Voronoi diagram for a set of nodes/sites $S$, to associate with a node $v \in S$ the subgraph $R(v)$ of $G$ induced by all the nodes strictly closer to $v$ than to any other node in $S$, measuring the length of a path by the sum of weights on the arcs. $R(v)$ is $v$'s _Voronoi region_. For example, the green nodes below are in $R(v_1)$, and the yellow nodes are in $R(v_2)$. <br /> ![enter image description here][1]<br /> I would like to understand the structure of the Voronoi diagram. As a start, what does the diagram of two sites $v_1$ and $v_2$ look like, i.e., what does the 2-site _bisector_ look like (blue in the above example)? I think of the bisector $B(v_1,v_2)$ as the complement of $R(v_1) \cup R(v_2)$ in $G$. Here are two specific questions: > Q1. Is the bisector of two sites connected in some sense? > Q2. Is $R(v)$ convex in the sense that it contains the shortest path between any two nodes in $R(v)$? Surely this has been studied before. Can anyone provide references/pointers? Thanks! <hr /> Addendum for Suresh's comment: <br /> ![enter image description here][2] <br /> [1]: https://i.sstatic.net/3yOr1.jpg [2]: https://i.sstatic.net/eq2P5.jpg