Finding cut sets of very large voxel set

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.

• 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? Jun 13 '13 at 14:37
• Each voxel is related to a 3D (integer) coordinate so can be viewed as a cube in space - basically generalizing pixels... Jun 13 '13 at 14:50
• Right, so how does a point in space have faces, edges, or vertices? Jun 13 '13 at 15:55
• Ok, let me rephrase. Jun 13 '13 at 15:58
• 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? Jun 13 '13 at 16:16