Volume identification from a graph where vertices refer to surfaces

Question

here's a question that's been bothering me for the last couple of days - my colleague believes this is a well-researched problem, but I couldn't find any papers online (perhaps the key words I used were incorrect). Given a graph where each vertex corresponds to a surface and an edge exists between two vertices if the corresponding surfaces meet at a line, how would I go about identifying the surfaces that combine to form closed volumes?

So for instance, the adjacency list for a cube (with surfaces numbered 1 to 6) might look something like this:

1 -> [4,2,5,6]
2 -> [1,3,5,6]
3 -> [2,4,5,6]
4 -> [3,1,5,6]
5 -> [1,2,3,4]
6 -> [1,2,3,4]

In addition to this information, I also know if some surfaces have free-edges (i.e those edges are not shared with any other surface) which means I can immediately exclude these surfaces since a surface with a free-edge cannot be part of a cavity boundary. Also, if two surfaces meet, they will meet cleanly at a boundary - no glancing blows etc.

What I hope to be able to do is not just identify that a cavity exists but also to output a mapping between surfaces and the cavities they contain. For instance, in the case of two cubes which meet at an edge (not enough reputation to post an image, so here's a side view):

-----------
|         |
|         |
|         |
---------------------
          |          |
          |          |
          |          |
          -----------

...this would be the desired output assuming surfaces 1-6 make up cube ONE and 7-12 make up cube TWO:

Volume 1 -> [1,2,3,4,5,6]
Volume 2 -> [7,8,9,10,11,12]

Note that, in this case, some surfaces have SIX neighbors in the graph while others have only FOUR neighbors.

Any help would be much appreciated!

Answer 1

Yes, this area is known as computational topology. Its central objects are algebraic groups of loops known as homology groups (H1 when loops are formed by 1-dim edges and H2 when we talk about 2-dim faces).

One can analyze such group by forming a homology group matrix. For some queries both H1 and H2 matrices are needed.

When matrix can be re-arranged into independent blocks it means shapes are not interacting. When a single-block homology matrix has ranking N it means shape has N cavities (holes). Simple shape like cube has 0 holes, torus has 1,etc.

One can find C++ and MATLAB open-source packages for these computations.

Hope it gives some helpful keywords.