2
$\begingroup$

I have an issue of finding the cut sets of large voxel sets. The voxels are assumed connected if they touch by face/edge/vertex (can vary), and ideally what I want is given any two members of the set to find a minimal cut set of voxels that separates them into two components.

The sets are 'large', 10^7 upwards, so I'm maybe looking at some kind of multi-res method? Any pointers be appreciated.

To clarify, voxels are assumed to exist on a 3D integral lattice, and we call them 'adjacent' if the coordinates vary by 1 in at most 1 (2, or 3) dimensions (for face/edge/vertex connectedness respectively). Voxels v0 and vN are connected if there is a sequence v0,..vi,vi+1,...vN where the vi,vi+1 are adjacent.

A component is a maximal set of connected voxels, and a cut set is any subset of a component whose removal will separate the component into 2 or more components.

$\endgroup$
10
  • $\begingroup$ Can you define what you mean by a voxel in this context? I've never considered a voxel set to be more than a cloud of points in 3D. Can you explain to us how a voxel can have a face, vertex, or edge? $\endgroup$
    – Bill Barth
    Jun 13, 2013 at 14:37
  • $\begingroup$ Each voxel is related to a 3D (integer) coordinate so can be viewed as a cube in space - basically generalizing pixels... $\endgroup$
    – Rrattz
    Jun 13, 2013 at 14:50
  • $\begingroup$ Right, so how does a point in space have faces, edges, or vertices? $\endgroup$
    – Bill Barth
    Jun 13, 2013 at 15:55
  • $\begingroup$ Ok, let me rephrase. $\endgroup$
    – Rrattz
    Jun 13, 2013 at 15:58
  • $\begingroup$ Each point has 3D integer coordinates. Call two points adjacent if their coordinates vary by 1 in at most 1 (2 or 3 depending on the kind of connectivity) dimensions. Call two points v0 and v1 connected if there is a sequence v0,...vi,vj...v1 where each vi,vj are adjacent. Does this clarify? $\endgroup$
    – Rrattz
    Jun 13, 2013 at 16:16

1 Answer 1

1
$\begingroup$

It looks like you're trying to solve a graph partitioning problem, with the constraint that two specific points be in different partitions. The library METIS is pretty popular for this application and can be run in parallel.

METIS might be overkill; it partitions the whole graph and thus looks at every point, whereas you just want to find a cut set and don't care about which side of the cut any of the other points end up on. Nonetheless, you can always read about how their algorithm works for inspiration. They use a multi-level approach, as you pointed out.

Moreover, your graph is highly structured. Any utility for partitioning general unstructured graphs probably won't take advantage of this.

For these reasons, you may be better off writing your own program if you need really fast performance and you're computing cut sets of lots of point pairs. Whether that's worth it is a judgment call you'll have to make.

$\endgroup$
2
  • $\begingroup$ Thanks, it certainly looks like a place to start and get some ideas- I'm not quite sure it's what I was after though. I'm sort of hoping to use the structure by implementing some type of 'imaging' type algorithm first as a pre-process before building a graph structure in the hopes that I can reduce the amount of graph I need to look at. $\endgroup$
    – Rrattz
    Jun 20, 2013 at 11:57
  • 1
    $\begingroup$ You might have success computing the fiedler vector directly via inverse iteration (or inverse arnoldi) of the graph laplacian. Since your graph is so structured, I think you could readily apply geometric multigrid for the "inverse" step. But this would be a very large programming effort, and ultimately I'd expect this to perform about the same as METIS. $\endgroup$ Jun 20, 2013 at 12:42

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.