# Voronoi diagram in a graph

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 Q1 to make sense you need some sense of faces, right? Otherwise, the "real" bisector is in the middle of edges, and introducing vertices just before and after this point, guarantees that the bisector is disconnected. Maybe if you assume the graph is chordal you can prove something. As for Q2: this is false even for geodesics in a polygon with holes (or terrains). My guess would be that you need to assume something quite strong on the graph to get non-trivial answer to both questions. – Sariel Har-Peled Dec 8 '11 at 20:09
• Thanks, Sariel, for those observations. Yes, it appears I was hoping for too much, and perhaps only in special classes of graphs will there be nice structural properties. – Joseph O'Rourke Dec 8 '11 at 21:50
• ah so on the regular sphere a voronoi cell can't get bigger than a hemisphere, so you don't have this problem. But my comment more generally was the same as Sariel's in that you're asking for convexity of voronoi cells in a potentially generic riemannian manifold and that's shouldn't be true. – Suresh Venkat Dec 8 '11 at 23:07
• For Q1, a simpler counterexample is the bisector of $S$ where $S$ is the left side of $K_{2, n}$. The bisector is totally disconnected. – Josephine Moeller Dec 9 '11 at 20:47
• So now I am thinking maybe there is an interesting question here. What if the underlying metric is a manifold (as suggested by Suresh). Now, we connect two points if and only if there exists a third point q, such the other two points are the two nearest neighbors (think about this as some kind of witness complex). A natural conjecture would be that if the manifold is doubling, then one can always add O(1) points such that the bisector is connected. Hmmm... – Sariel Har-Peled Dec 11 '11 at 5:55