Mesh Adaptivity

The research problem we are trying to solve right now is based on this paper. The paper describes a tetrahedral mesh adaptivity scheme based on "edge markings". Each face (2-cell) of a tetrahedron has one of its edges (1-cells) marked. A set of markings is valid if the following are true:

1. Whenever two tetrahedrons share a face, that face is marked the same way in each of the tetrahedrons. (That is, each face has a unique marking, even if it's in more than one tetrahedron.)

2. In each tetrahedron, there exists an edge that is marked on both of the faces that contain it.

The paper shows how to use these markings to do refinement. The problem we are trying to figure out is how to do coarsening. In particular, when you coarsen the mesh by contracting an edge to nothing, you merge pairs of opposite faces into one face, so the question is how to change the markings so that it is still valid. We want to do this in a way that involves changing the fewest number of markings.

There are a few different ways we can go about doing this:

1. The method described in the paper about how to set up the initial markings says that we can establish a total order over all the edges, then have each face mark the edge that is first in that order. This raises the question of whether or not this property - that there exists a total order over the edges such that the marked edge in each face is the first in that total order - is preserved over the refinement process. If so, then we have a simple algorithm for merging two faces when doing refinement: just choose one of the faces arbitrarily and have the new edges inherit that edge's position in the order, then remark them according to that order. This obviously will not affect any tetrahedron that doesn't contain one of the edges that was just merged, so we can keep the re-marking down to a small number of tetrahedrons.

When we generate a tetrahedron of type P, all the marked edges don't include the new vertex, so the property is preserved if we just put all the new edges last in the partial order. When we generate a tetrahedron of type A, it is a little more complicated - the property is still preserved but we have to put some of the edges between other edges in the order (I'll put a diagram up soon.) There is still a complication of when we generate a new tetrahedron where the new vertex was already generated (by refining a different tetrahedron that the refined edge was also a part of) because now we have to make sure that the same position for that edge in the order will satisfy the conditions on both of the faces I'm not sure yet if that's actually satisfied.

2. We could look at relations between this problem and the Boolean satisfiability problem (SAT). This problem has a very natural Boolean-satisfiability representation: the proposition "face F has edge E marked" is one of the variables for each pair (F,E), then the conditions that each face has exactly one edge marked as well as the conditions (1) and (2) above are easily expressed. If we wanted to try to minimize the number of changes we have to make then we could think of it as a sort of weighted maximum satisfiability problem where we try to also satisfy as many of the propositions "marking X wasn't changed" as possible. We could then use a MaxSAT solver like this one to figure out the best solution. This direction is probably not the best way of doing it because we have to convert the problem to a different form, solve it, and convert the answer back, plus the size of the problem will be the size of the whole mesh and we really want to only look at a small neighborhood of cells (for parallelization purposes if nothing else).

Another approach is to try to reduce the satisfiability problem to our problem; that would show that it is NP-complete. Of course that wouldn't give us an actual algorithm; it would just tell us we should stop looking for an exact polynomial-time algorithm. So this would be nice to have but isn't the first direction we should look.

3. Another way to think about the problem is to imagine each possible "switch" of an marking on one face from one edge to another edge as a node in a directed graph. Suppose that we switch a marking on a face of one tetrahedron to make the markings on that tetrahedron valid. That may make the markings on the adjacent tetrahedron (the one on the "other side" of that face) not valid because we also have to switch that marking on that tetrahedron. That may require switching yet another marking, and so on. Note that any position is only one "marking switch" away from a valid position, so we only have to do one marking switch at each step. In the directed graph, for each marking switch that necessitates another marking switch, put an edge to the possible choices of marking switches to make it valid, and for those marking switches that will make it valid on both sides and allow you to halt the process, mark those as "end nodes." Then the problem is just to find the shortest path from the change you are forced to make due to the merging to an end node, which is a simple matter of breadth-first search (or Dijkstra's algorithm, if we want to weight the marking switches by "how hard" they are to make). It will probably end up a little more complicated because an edge contraction affects lots of faces rather than just one.

I'll try to post up some more ideas in the next couple days.