<p>Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs.
Information Processing Letters 27, 125–128 (1988)</p>

<p>Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156–163
(2000)</p>

<p>both references copied from</p>

<p>Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks. Transactions on Computational Science 14: 211-238 (2011)</p>

CC BY-SA 3.0
2011-12-08T17:01:56.970Z
This will take some digging, but superficially, it does not seem that many structural properties of the diagram have been identified in these papers (perhaps because there are few properties of note!).
Joseph O'Rourke
CC BY-SA 3.0
2013-05-13T22:39:55.247Z
indeed not much seems to be known;
we have another lemma or two in http://www.sommer.jp/voronoi.htm
Christian Sommer
CC BY-SA 3.0
2011-12-08T16:25:33.563Z
2011-12-08T16:25:33.563Z
David Eppstein
<p>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 <em>Voronoi region</em>.
For example, the green nodes below are in $R(v_1)$, and the yellow nodes
are in $R(v_2)$.
<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="https://i.sstatic.net/3yOr1.jpg" alt="enter image description here"><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 <em>bisector</em> 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:</p>

<blockquote>
  <p>Q1. Is the bisector of two sites connected in some sense?</p>
  
  <p>Q2. Is $R(v)$ convex in the sense that it contains the shortest path between any two
  nodes in $R(v)$?</p>
</blockquote>

<p>Surely this has been studied before.  Can anyone provide references/pointers?
Thanks!
<hr />
Addendum for Suresh's comment:
<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="https://i.sstatic.net/eq2P5.jpg" alt="enter image description here">
<br /></p>

CC BY-SA 3.0
2011-12-08T18:22:35.597Z
Regarding Q2: Surely this should be no in general, because it's not true for Riemannian manifolds in general (cf the sphere). Might be interesting to ask what the discrete equivalent of the injectivity radius.
Suresh Venkat
CC BY-SA 3.0
2011-12-08T19:52:51.657Z
@Suresh: Could you expand your remark to indicate how one achieves nonconvexity on the sphere?
Joseph O'Rourke
CC BY-SA 3.0
2011-12-08T20:09:28.640Z
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
CC BY-SA 3.0
2011-12-08T21:50:11.700Z
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
CC BY-SA 3.0
2011-12-08T23:07:30.680Z
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
CC BY-SA 3.0
2011-12-09T00:21:55.473Z
@Suresh: Yes, I see now, sorry for not catching your point immediately!
Joseph O'Rourke
CC BY-SA 3.0
2011-12-09T20:47:38.270Z
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
CC BY-SA 3.0
2011-12-11T05:55:45.623Z
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
<reference-request><graph-theory><cg.comp-geom>
Voronoi diagram in a graph
Joseph O'Rourke
# Voronoi diagram in a graph

(Asked by: username_0 on 2011-12-08)

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)$.
  
          ![enter image description here](https://i.sstatic.net/3yOr1.jpg)  
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](https://i.sstatic.net/eq2P5.jpg)

**Tags:** reference-request, graph-theory, cg.comp-geom
> **Comments:**
> **username_1**: Regarding Q2: Surely this should be no in general, because it's not true for Riemannian manifolds in general (cf the sphere). Might be interesting to ask what the discrete equivalent of the injectivity radius.  
> **username_0**: @Suresh: Could you expand your remark to indicate how one achieves nonconvexity on the sphere?  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: @Suresh: Yes, I see now, sorry for not catching your point immediately!  
> **username_3**: 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.  
> **username_2**: 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...  

---

## 1 answers

### Answer by username_4 on 2011-12-08. Score: 8

Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs.
Information Processing Letters 27, 125–128 (1988)

Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156–163
(2000)

both references copied from

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks. Transactions on Computational Science 14: 211-238 (2011)

> **Comments:**
> **username_0**: This will take some digging, but superficially, it does not seem that many structural properties of the diagram have been identified in these papers (perhaps because there are few properties of note!).  
> **username_5**: indeed not much seems to be known; we have another lemma or two in http://www.sommer.jp/voronoi.htm  

---

