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)$.
          
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!

---

For Suresh's comment:
          ![enter image description here][2]

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)$.
          
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!

---

Addendum for Suresh's comment:
          ![enter image description here][2]

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)$.
          
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!

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)$.
          
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!

---

For Suresh's comment:
          ![enter image description here][2]