I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are also coincident. There are some faces that are exposed. I can use this information to create an adjacency graph, where each node in the graph represents a tetrahedron and has at most 4 direct neighbors. Two nodes in the graph are adjacent if the tetrahedra they represent are adjacent along a face.

My problem now is to minimize the number of disjoint groups of vertices in the graph such that each sub-graph is not disconnected. I must also meet the criteria that for all sub-graphs, the accumulative 3D structure formed from the tetrahedra represented by the nodes in the sub-graph is convex. That is, after removal of the unexposed faces, all of the vertices of the remaining structure fall on or to one side of the plane of each exposed face.

I am interested in an algorithm with complexity much lower than the Bell numbers because I might need to run it on a large data set.

This is the 2D equivalent of the problem which is much easier to visualize: http://i.stack.imgur.com/riKWq.png

There are two optimal solutions, each with 2 sub-groups. The first is [{1,2,3,4,5,6,7,8,9,10,11,12}, {13}], and the second is [{1,2,3,4,5,6,7,8,9,10,11}, {12,13}].

  • $\begingroup$ So your problem is to decompose your polyhedron in a minimal number of convex subpolyhedrons? $\endgroup$ – Nicolas Malebranche Jan 22 '16 at 14:17
  • $\begingroup$ Yes, preferred to be non-overlapping and minimal. However I would accept near-minimal approximations at this point. $\endgroup$ – John Jan 22 '16 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.