<p>One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.</p>

CC BY-SA 3.0
2012-08-24T05:09:20.193Z
2012-08-24T05:09:20.193Z
Sariel Har-Peled
<p>I don't see how the fact that the graph results from a voronoi diagram substantially changes the problem. You have a graph and want to do a k-cut, where k is the number of your workers. Instead of minizing just the cut, you also want to make the partitions equal in size.</p>

<p>There is a ridiculously simple heuristic for k-kut. Pick an edge at random and merge the nodes at both endpoints. Repeat, until desired number of components is reached. Try again from the beginning, until bored. Output best result.</p>

<p>This works, because expensive cuts have lots of edges that could get picked, while cheap cuts have few and are therefore selected less often.</p>

<p>Normally, the problem is formulated with edge weights, and edges get picked at nonuniform probabilities, scaled by their weight. If you would instead pick edges with probabilities scaled in such a way, that it favors equally sized components, it should be possible to find a heuristic that gets good results for both minimizing cut size and spreading nodes equally.</p>

<p>I'd suggest to weight the edges according to the number of nodes in the original graph that the resulting node would represent. Edges which represent multiple edges in the original graph, should also get higher probability (their weights start at one, but must still be aggregated on a merge). The resulting probability to pick an edge would be: (number of edges in the original graph the edge represents) / (number of nodes both endpoints represent in the original graph, combined). Off course, this needs to be normalized to 1.</p>

<p>In this way the components would grow at roughly equal speeds, and components which are well connected are merged together with higher preference. I just tried this with a small pen and paper example, and it seems to actually work out just like that.</p>

<p>Depending on whether your problem suffers more from unequal work loads or too much network access, you can tune the probabilities to prefer merging due to high edge count over merging due to low node count or vice versa.</p>

CC BY-SA 3.0
2012-08-18T21:35:31.667Z
2012-08-18T21:48:18.790Z
2012-08-18T21:48:18.790Z
Shadow
<p>Non-optimal tricks I might use:</p>

<p>1) Use a force directed graph drawing program, then use the layout coordinates to generate a quadtree(z-curve).</p>

<p>2) Use k-means, with k= 3, and distance being the shortest path length. Then recursively apply the kmeans to each cluster. You will get something close to the notion of a space filling curve. When you subdivide one cell into three, use the distance between the generator for each of the three children and the two generators of the other two parent level cells to determine the ordering. For the highest level ordering just pick something. </p>

CC BY-SA 3.0
2012-05-15T21:46:43.077Z
Not sure why I picked k=3, guess it just felt more like a SFC if I applied it to a 2d grid graph. With k=2 you should get a layout that looks more like a k-d tree.
Chad Brewbaker
CC BY-SA 3.0
2012-05-15T21:43:34.347Z
2012-05-15T21:43:34.347Z
Chad Brewbaker
<p>I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.</p>

<p>Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.</p>

<p>I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.</p>

CC BY-SA 3.0
2012-01-15T21:44:20.480Z
cause I didn't know that it was about graph theory in the beginning. I now got hints that I'm after kernighan-lin algorithm.
Dima
CC BY-SA 3.0
2012-05-13T17:44:27.543Z
On the z-order, points that are close in the original space are often, *but not guaranteed to be* close to each other in the z order.
Joe
CC BY-SA 3.0
2012-05-15T16:20:26.440Z
downvoting: it's not clear what the OP is asking. if he wants z-order, then there is no question. otherwise please define "locality preserving order": is this just a low distortion embedding onto a line? the graph-theory part confuses matters even more. which one of the several dozen defenitions of community are we to assume? the link given points to Newman's modularity, but then he mentions kernighan-lin which is a heuristic for sparse cut. is the question about algorithms to maximize modularity?
Sasho Nikolov
CC BY-SA 3.0
2012-05-15T20:32:25.307Z
@SashoNikolov I have a 3D veronoi diagram. I have a computation algorithm: for each node compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.
Dima
CC BY-SA 3.0
2012-05-15T20:54:32.147Z
so are you looking  to partition a planar graph into some specified number of balanced parts while minimizing the number of edges that go between the parts? something like a $k$-part generalization of balanced cut on a planar graph? if so, you can update your question and you'll probably get more useful answers. for definition of balanced cut: http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture18.pdf
Sasho Nikolov
CC BY-SA 3.0
2012-05-15T21:30:16.250Z
So you have the neighbor graph between Voronoi cells; but somehow the coordinates of these cells were stripped so all you are left with is the graph, but you want some nice linear ordering on the vertices of the graph data that will mirror the spatial locality preserving quadtree/SFC you would otherwise use?  Well, you could throw a force directed layout algorithm at it, map it to 2d/3d space, construct the quadtree, then use that ordering.
Chad Brewbaker
CC BY-SA 3.0
2012-05-18T17:34:22.543Z
revorked the question a little bit. Hope it is better now...
Dima
<ds.data-structures><cg.comp-geom><delaunay-triangulation>
How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?
Dima
# How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

(Asked by: username_0 on 2012-01-09)

I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.

Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.

I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.

**Tags:** ds.data-structures, cg.comp-geom, delaunay-triangulation

> **Comments:**
> **username_0**: cause I didn't know that it was about graph theory in the beginning. I now got hints that I'm after kernighan-lin algorithm.  
> **username_1**: On the z-order, points that are close in the original space are often, *but not guaranteed to be* close to each other in the z order.  
> **username_2**: downvoting: it's not clear what the OP is asking. if he wants z-order, then there is no question. otherwise please define "locality preserving order": is this just a low distortion embedding onto a line? the graph-theory part confuses matters even more. which one of the several dozen defenitions of community are we to assume? the link given points to Newman's modularity, but then he mentions kernighan-lin which is a heuristic for sparse cut. is the question about algorithms to maximize modularity?  
> **username_0**: @SashoNikolov I have a 3D veronoi diagram. I have a computation algorithm: for each node compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.  
> **username_2**: so are you looking  to partition a planar graph into some specified number of balanced parts while minimizing the number of edges that go between the parts? something like a $k$-part generalization of balanced cut on a planar graph? if so, you can update your question and you'll probably get more useful answers. for definition of balanced cut: http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture18.pdf  
> **username_3**: So you have the neighbor graph between Voronoi cells; but somehow the coordinates of these cells were stripped so all you are left with is the graph, but you want some nice linear ordering on the vertices of the graph data that will mirror the spatial locality preserving quadtree/SFC you would otherwise use?  Well, you could throw a force directed layout algorithm at it, map it to 2d/3d space, construct the quadtree, then use that ordering.  
> **username_0**: revorked the question a little bit. Hope it is better now...  

---

## 3 answers

### Answer by username_4 on 2012-08-24. Score: 1

One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.


---

### Answer by username_5 on 2012-08-18. Score: 0

I don't see how the fact that the graph results from a voronoi diagram substantially changes the problem. You have a graph and want to do a k-cut, where k is the number of your workers. Instead of minizing just the cut, you also want to make the partitions equal in size.

There is a ridiculously simple heuristic for k-kut. Pick an edge at random and merge the nodes at both endpoints. Repeat, until desired number of components is reached. Try again from the beginning, until bored. Output best result.

This works, because expensive cuts have lots of edges that could get picked, while cheap cuts have few and are therefore selected less often.

Normally, the problem is formulated with edge weights, and edges get picked at nonuniform probabilities, scaled by their weight. If you would instead pick edges with probabilities scaled in such a way, that it favors equally sized components, it should be possible to find a heuristic that gets good results for both minimizing cut size and spreading nodes equally.

I'd suggest to weight the edges according to the number of nodes in the original graph that the resulting node would represent. Edges which represent multiple edges in the original graph, should also get higher probability (their weights start at one, but must still be aggregated on a merge). The resulting probability to pick an edge would be: (number of edges in the original graph the edge represents) / (number of nodes both endpoints represent in the original graph, combined). Off course, this needs to be normalized to 1.

In this way the components would grow at roughly equal speeds, and components which are well connected are merged together with higher preference. I just tried this with a small pen and paper example, and it seems to actually work out just like that.

Depending on whether your problem suffers more from unequal work loads or too much network access, you can tune the probabilities to prefer merging due to high edge count over merging due to low node count or vice versa.


---

### Answer by username_3 on 2012-05-15. Score: 0

Non-optimal tricks I might use:

1) Use a force directed graph drawing program, then use the layout coordinates to generate a quadtree(z-curve).

2) Use k-means, with k= 3, and distance being the shortest path length. Then recursively apply the kmeans to each cluster. You will get something close to the notion of a space filling curve. When you subdivide one cell into three, use the distance between the generator for each of the three children and the two generators of the other two parent level cells to determine the ordering. For the highest level ordering just pick something.

> **Comments:**
> **username_3**: Not sure why I picked k=3, guess it just felt more like a SFC if I applied it to a 2d grid graph. With k=2 you should get a layout that looks more like a k-d tree.  

---

