10
$\begingroup$

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
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

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Commented Dec 8, 2011 at 20:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 8, 2011 at 21:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Dec 8, 2011 at 23:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – Josephine Moeller
    Commented Dec 9, 2011 at 20:47
  • 1
    $\begingroup$ 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... $\endgroup$
    – Sariel Har-Peled
    Commented Dec 11, 2011 at 5:55

1 Answer 1

Reset to default
8
$\begingroup$

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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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!). $\endgroup$
    – Joseph O'Rourke
    Commented Dec 8, 2011 at 17:01
  • $\begingroup$ indeed not much seems to be known; we have another lemma or two in sommer.jp/voronoi.htm $\endgroup$
    – Christian Sommer
    Commented May 13, 2013 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.