A new formulation

I have come up with a new formulation of the theorem in the last post that allows us to weaken the conditions necessary (and also make the proof a bit simpler). I also cleaned up the definitions a bit. Here is the new proof.

DEFINITIONS:

A "mark set" M is defined by a function M(f) that maps faces to edges in those faces. The domain of M, denoted by d(M), is a subset of the faces in the mesh.

A face f is "set by M" if f is in d(M).

An edge e is "marked by M" if there exists a face f such that M(f)=e. (In other words, e is in the range of M.)

M is "complete" if d(M) includes all the faces in the mesh.

Two mark sets M and N are "complementary" if the union of d(M) and d(N) is all the cells in the mesh, and the intersection of d(M) and d(N) is null.

The sum M+N of two mark sets whose domains are disjoint is defined so that:

(M+N)(f) = M(f), if f is in d(M),
(M+N)(f) = N(f), if f is in d(N),
and (M+N)(f) is undefined, if f is in neither d(M) nor d(N).

M is "consistent for C" (where C is a cell) if there exists an edge e in C such that M(f)=M(g)=e, where f and g are the two faces in C that contain e.

M is "valid" if for each cell C such that all four of the faces of that cell are set by M, M is consistent for C.

CLAIM:

Consider a mesh with two complementary mark sets defined on that mesh: M and K.

If the following condition is true:

(1) For each cell C, at most two of its edges are marked by K.

Then is is possible to find a set N whose domain is identical to that of M such that:

(2A) N+K is a valid mark set. (It is also complete by construction.)
(2B) For any face x that does not contain at least one edge marked by K, we have N(x)=M(x).

PROOF:

Consider the mark set N defined (over the same domain as M) as follows:

(3A) If the face f does not contain any edges that are marked by K, then N(f) := M(f).
(3B) If the face f does contain an edge that is marked by K, then N(f) := x, where x is one of those edges. (If there are more than one of those edges, we can choose arbitrarily.)

The following lemma is easy to see is true by construction:

(L) If the face f (where f is any face in the mesh) contains an edge that is marked by K, then (N+K)(f) equals one of those edges.

Also, by construction, N satisfies (2B) above. We must now show that N+K is valid.

Consider any cell C in the mesh. There are several possibilities:

(4A) C contains zero edges that are marked by K. Then all of C's faces are set by M, and (3A) is applied for all of C's faces, so the markings of C's faces in (N+K) are the same as the markings of C('s faces in M, which we know is consistent by validity of M.

(4B) C contains exactly one edge that is marked by K; call it e. Then by L, we have (N+K)(f)=(N+K)(g)=e, where f and g are the two faces in C that contain e. Thus we know N+K is consistent for C.

(4C) C contains exactly two edges that are marked by K. If these edges do not share a vertex, they thus are not both contained in the same face, and the argument in (4B) applies to each of the edges. If the edges do share a vertex, that means that both of the edges are contained in one face, and each edge is also contained in another face that it doesn't share with the other edge. Suppose that the two edges are e and f, and e is contained in faces x and y, and f is contained in faces x and z. By (L) we have (N+K)(y) = e, and (N+K)(z) = f. We have that (N+K)(x) can equal either e or f, and we don't know which, but whichever one it equals it will still satisfy the consistency condition.

----

The way we use this proceeds as before - put all the faces that got merged in K, and put the existing markings for the rest of the faces in M.