A performance result

DEFINITION:

We will use "edges", "faces", and "cells" to mean 1-cells, 2-cells, and 3-cells respectively. (This terminology is appropriate here because of the unique role played by each dimension of cell in this problem.)

A set of marks M is defined by a function M(x) that maps faces to the edges that are marked in them. If a face is shared by two cells, it is considered just one face.

An edge e is "marked by M" if there exists at least one cell x such that M(x)=e.

CLAIM:

Suppose we have a mesh that is validly marked - call this set of marks M. Then suppose we take a subset L of the faces in that mesh, which we will call the "locked" faces. Define a function K(x) that maps each face in L to one of its edges. (Effectively, L and K(x) define a partial set of marks. This set does not need to coincide with M in any way. We define "marked by K" in the same manner that we defined "marked by M" above.)

Also, note that M doesn't have to be a complete set of marks; we don't have to specify values of M(f) for faces f that are in L (and M only has to satisfy the condition that each cell has an edge that is marked twice for those cells that have values of M(f) for all four faces; see below).

If the following conditions are true:

(1A) On each cell, at most one face is locked.
(1B) Any non-locked face shares an edge with at most one locked cell.

Then there exists a valid set of markings N of the mesh such that:

(2A) For any face x in L, N(x) = K(x).
(2B) For any face x that does not contain at least one edge that is marked by K, N(x) = M(x).

PROOF:

Consider the function N(x) defined as follows:

(3A) If x is in L, then N(x) = K(x).
(3B) If x is not in L but it contains an edge marked by K, then N(x) equals that edge. (Note that by condition 1B, it is impossible for x to contain two edges each marked by K.)
(3C) Otherwise, N(x) = M(x).

By construction, this function satisfies conditions 2A and 2B above. We now must show that this set of markings is valid.

Consider any cell C. There are several possibilities:

(4A) Suppose none of the edges in C are marked by K. Then (3C) is used for all faces in C, so the set of markings for that cell in N is the same as that in M, and we know M is valid for C by hypothesis.

(4B) Suppose there exists an edge e in C that is marked by K, but no cells in C are in L. Then there will be two faces in C, call them f and g, that contain e. By (3B), we have N(f)=N(g)=e, so C is validly marked since two of its faces share a marked edge.

(4C) Suppose there exists a face f in C that is in L. Let e=K(f). By (2A), we know that e=N(f). Also, C has another face g that also contains e. By (1A), g is not locked, so by (3B) we have e=N(g), which means f and g share a marked edge and thus the cell is validly marked.

-----

So, what does all this mean for our original problem? Well, let's say we have our original mesh, and then we contract an edge. Put all the faces that got "merged" by that edge contraction in L, and for the rest, keep the original markings and call it M. Now whatever we set the markings in L to, we can guarantee that we won't have to change the markings on any cell that isn't adjacent to one of the edges we just marked in L. This means that we have an effective upper bound on how many cells we will have to change, and also means that we have a simpler optimization problem since we just have to look at how to mark the cells in L, and let the algorithm above do the rest.

Of course this is contingent on the conditions 1A and 1B above being true, but those shouldn't be too hard to satisfy.