Introduction
Cell structures appear throughout the natural world. Examples include the decomposition of a polycrystalline material into its constituent grains (Figure 1 a) and the representation of a biological tissue as a union of cells (Figure 1 b). Recent advances in microscopy techniques have made possible the collection of large datasets of two-dimensional images of cell structures, and for some specific applications three-dimensional images are available as well [3 ] [4, 5, 6]. The underlying physical processes are often stochastic though, and the analysis of the resulting images continues to be challenging. Specifically, the scarcity of established techniques to compare such images, or even to identify natural classes, has significant practical consequences. For example, it is difficult to evaluate whether a simulated material microstructure is a reasonable approximation of a manufactured one without the ability to quantitatively measure the extent of their differences. As a second example, there would
Figure 1. (a) A micrograph of a metal showing the polycrystal microstructure, reprinted from Ref. [1 ] , Fig. 4, with permission from John Wiley and Sons. (b) A histopathology slide of cancerous bone tissue [2 ] .
be considerable implications for human health if a computer vision model could be trained on the histopathological classification problem to distinguish images of healthy and cancerous biological tissues.
Previous literature on this subject has generally either (i) treated the image as an array of greyscale or colored pixels and applied general image analysis techniques, or (ii) compared ad hoc selections of geometric statistics for individual or small groups of cells. While the former does not require expert knowledge and can be highly accurate for specific applications [7, 8], the performance rapidly degrades for structures outside the support of the training set, and the analysis usually does not indicate which image features are most significant. The latter instead uses expert knowledge to identify the geometric features most relevant to the properties of interest [9, 10], but this effectively prohibits meaningful comparison with structure classes for which the selected features are irrelevant or undefined [11]. It is also significant that both approaches are practically limited to comparatively small sets of cell structures for which the extent of geometric variation is known beforehand. This can increase the difficulty of analyzing newly-discovered cell structures, discourage the intentional design and exploration of cell structures outside of well-established classes, and promote the fragmentation of the physical science communities concerned with such systems. This situation has motivated several recent studies that have sought to develop comprehensive and general geometric summaries of the overall cell arrangement, ideally providing sufficient information to reliably identify structural differences and predict system properties while remaining flexible enough to be useful for the analysis of general cell structures.
Here we introduce two dissimilarities between cell structures called the one-to-one volume exchange metric and the many-to-many volume exchange dissimilarity. Intuitively, they measure the minimum amount of volume that must be swept out by the cell boundaries to transform one structure into the other, as for example in Figure 2 . The one-to-one volume exchange metric additionally requires that each cell in one structure either transforms into exactly one cell in the other structure or disappears in the process. The many-to-many volume exchange dissimilarity instead allows initially non-adjacent cells to merge during the transformation. One advantage that these have over alternatives like the Hausdorff metric is that they are less sensitive to the geometric noise that is often introduced either by the imaging method or by the cell segmentation process.
Figure 2. (Left) A cellular filling W \mathcal{W} W between P \mathcal{P} P and Q \mathcal{Q} Q that realizes the minimal one-to-one volume exchange. (Right) The projection into the plane shows the volume exchange distance between P \mathcal{P} P and Q \mathcal{Q} Q as the area in grey.
The underlying physical motivation though is that there are many examples of cell structures for which the transport of volume across the cell boundaries is the slowest (rate-limiting) process involved in changing the cell configuration, and geometric properties that are the slowest to change are likely to be highly significant to physical systems. With reference to Figure 1 , cell boundary motion in a polycrystal occurs precisely by atoms leaving one grain, passing through the boundary, and joining the crystal lattice of the adjoining grain. A biological cell of fixed volume is easily able to redistribute the contents of the cell, but the volume changes that accompany general cell configuration changes involve a slower process of water transport across the cell membrane. Gas transport through the liquid boundaries of the bubbles in a dry soap foam is so slow relative to other processes that in the limit the cell configuration is entirely specified by the topology of the cell boundary network and the cell volumes. These examples suggest that meaningful dissimilarities could be based directly on the amount of volume exchanged by adjoining cells rather than on, e.g., changes to the area of the cell boundaries or the amount of displacement of the cell boundaries.
The dissimilarities can also be motivated by considering distances on labeled cell structures, with there being many applications for which there is a natural set of labels in a metric space ( Y , δ ) (Y,\delta) ( Y , δ ) . For example, in materials science the grains of a polycrystalline material could be labeled by a crystal orientation that indicates the misorientation of the crystal lattice relative to a suitable reference, i.e., an element of the quotient Y = S O ( 3 ) / H Y = SO(3)/H Y = S O ( 3 ) / H of the three-dimensional rotation group S O ( 3 ) SO(3) S O ( 3 ) by the point symmetry group H H H of the crystal lattice [12]. Such a labeled cell structure P \mathcal{P} P in an ambient space Ω ⊂ R n \Omega\subset\mathbb{R}^{n} Ω ⊂ R n can be identified with a piecewise constant function p : Ω → Y p:\Omega\to Y p : Ω → Y whose level sets are the cells. A natural distance between cell structures P \mathcal{P} P and Q \mathcal{Q} Q is then given by the L 1 L^{1} L 1 norm of δ ( p , q ) \delta(p,q) δ ( p , q ) . However, in the absence of specific knowledge about the cell labels or a natural distance between them, minimal assumptions could be that labels on adjacent cells are distinct and that distinct labels are a unit distance apart. Given two cell structures P \mathcal{P} P and Q \mathcal{Q} Q , the many-to-many volume exchange dissimilarity is then the minimal L 1 L^{1} L 1 distance between g P g_{\mathcal{P}} g P and g Q g_{\mathcal{Q}} g Q over all possible labeling g P g_{\mathcal{P}} g P and g Q g_{\mathcal{Q}} g Q which assign distinct labels to adjacent cells. The one-to-one volume exchange metric—a true metric which is more efficient to compute in practice—is obtained by adding the further assumption that the labels are distinct for each cell in a cell structure regardless of adjacency.
We now formally define cell structures, transformations between them called cellular fillings, and the volume exchange metric and dissimilarity. A cell structure in Ω ⊂ R n \Omega\subset\mathbb{R}^{n} Ω ⊂ R n is a countable partition P \mathcal{P} P of Ω \Omega Ω so that each cell E ∈ P E \in\mathcal{P} E ∈ P has positive Lebesgue measure, and the collection has finite interfacial surface energy (see Definition 8 for a precise definition). We assume that Ω \Omega Ω is open bounded open and connected, and we consider two cell structures to be equal if they differ up to a rearrangement of a set of measure zero. We do not make assumptions about the topology of cells, but call them “cells” because of the proposed applications.
We introduce two different ways to “fill” the space between two n n n -dimensional cell structures P , Q \mathcal{P},\mathcal{Q} P , Q defined on the ends of a cylinder Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) . Either notion defines an ( n + 1 ) (n+1) ( n + 1 ) -dimensional cell structure W \mathcal{W} W of Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) . To avoid pathologies, we introduce the notions of essential interior and essential boundary from geometric measure theory. With the notion of the density of E ⊂ R n E \subset\mathbb{R}^{n} E ⊂ R n at x x x ,
Θ ( E , x ) : = lim r → 0 + L n ( E ∩ B ( x , r ) ) L n ( B ( x , r ) ) , \Theta(E,x) := \lim_{r\to0+} \frac{\mathcal{L}^{n}(E \cap B(x,r))}{\mathcal{L}^{n}(B(x,r))}, Θ ( E , x ) := r → 0 + lim L n ( B ( x , r )) L n ( E ∩ B ( x , r )) ,
we can define the essential interior E ( 1 ) E^{(1)} E ( 1 ) of E E E consists of the set of points where the density of E E E is 1, and the essential boundary ∂ ∗ E \partial^{*}E ∂ ∗ E of E E E consists of the points where the density of E E E is not in { 0 , 1 } \{0,1\} { 0 , 1 } . In particular, if we define adjacency of cells via their essential boundaries, the adjacency is unchanged by rearranging a set of Lebesgue measure zero (for instance, adding a path connecting one cell to another).
A one-to-one cellular filling between cell structures P \mathcal{P} P and Q \mathcal{Q} Q is an ( n + 1 ) (n+1) ( n + 1 ) -dimensional cell structure W \mathcal{W} W in Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) so that for each cell W ∈ W W \in\mathcal{W} W ∈ W with H n ( ∂ ∗ W ∩ ( Ω × 0 ) ) > 0 \mathcal{H}^{n}(\partial^{*}W \cap(\Omega\times0)) > 0 H n ( ∂ ∗ W ∩ ( Ω × 0 )) > 0 , there exists a cell E ∈ P E \in\mathcal{P} E ∈ P such that
H n ( ( E × 0 ) △ ∂ ∗ W ∩ ( Ω × 0 ) ) = 0 , \mathcal{H}^{n}\bigl((E \times0) \mathbin{\triangle} \partial^{*}W \cap(\Omega\times0)\bigr)=0, H n ( ( E × 0 ) △ ∂ ∗ W ∩ ( Ω × 0 ) ) = 0 ,
and similarly for a cell W ∈ W W \in\mathcal{W} W ∈ W with H n ( ∂ ∗ W ∩ ( Ω × 1 ) ) > 0 \mathcal{H}^{n}(\partial^{*}W \cap(\Omega\times1)) > 0 H n ( ∂ ∗ W ∩ ( Ω × 1 )) > 0 .
Call two cells of a cell structure P \mathcal{P} P adjacent if the intersection of their essential boundaries has positive ( n − 1 ) (n-1) ( n − 1 ) -dimensional Hausdorff measure. A coarsening of a cell structure P \mathcal{P} P is a cell structure P ′ \mathcal{P}' P ′ so that each E ′ ∈ P ′ E' \in\mathcal{P}' E ′ ∈ P ′ is a union of non-adjacent cells of P \mathcal{P} P . A many-to-many cellular filling between cell structures P \mathcal{P} P and Q \mathcal{Q} Q in Ω \Omega Ω is a one-to-one cellular filling between coarsenings of P \mathcal{P} P and Q \mathcal{Q} Q . See Figure 3 .
Figure 3. (Left) A many-to-many cellular filling W \mathcal{W} W between P \mathcal{P} P and Q \mathcal{Q} Q that is not a one-to-one cellular filling. Note that two cells are merged via a pair of pants. (Right) The projection into the plane shows the volume exchange dissimilarity between P \mathcal{P} P and Q \mathcal{Q} Q as the area in grey.
Denote the collections of such fillings by F 1 ( P , Q ) \mathcal{F}^{1}(\mathcal{P},\mathcal{Q}) F 1 ( P , Q ) and F 2 ( P , Q ) \mathcal{F}^{2}(\mathcal{P},\mathcal{Q}) F 2 ( P , Q ) , respectively. The restriction on one-to-one fillings may seem artificial as they do not allow a single connected cell to be transformed into two disjoint connected cells via a “pair of pants,” but as we will see below the resulting metric has nicer properties and is easier to compute.
Let W \mathcal{W} W be an ( n + 1 ) (n+1) ( n + 1 ) -dimensional cell structure in Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) , let ∂ ∘ W \partial^{\circ}\mathcal{W} ∂ ∘ W the union of the essential boundaries of the elements of the partition W \mathcal{W} W , in the open cylinder, i.e.,
∂ ∘ W = ⋃ W ∈ W ∂ ∗ W ∩ ( Ω × ( 0 , 1 ) ) \partial^{\circ}\mathcal{W}=\bigcup_{W\in\mathcal{W}}\partial^{*}W\cap(\Omega\times(0,1)) ∂ ∘ W = W ∈ W ⋃ ∂ ∗ W ∩ ( Ω × ( 0 , 1 ))
and let π : Ω × ( 0 , 1 ) → Ω × 0 \pi:\Omega\times(0,1)\to\Omega\times0 π : Ω × ( 0 , 1 ) → Ω × 0 be the projection. We define the volume exchange of a filling W \mathcal{W} W by
E [ W ] = ∫ Ω × 0 H 0 ( ∂ ∘ W ∩ π − 1 ( x ) ) d L n ( x ) = ∫ ∂ ∘ W ∣ ⟨ v , n ( x ) ⟩ ∣ d H n ( x ) , (1) \mathcal{E}[\mathcal{W}]=\int_{\Omega\times0}\mathcal{H}^{0}\bigl(\partial^{\circ}\mathcal{W}\cap\pi^{-1}(x)\bigr)\,d\mathcal{L}^{n}(x)=\int_{\partial^{\circ}\mathcal{W}}|\langle v,n(x)\rangle|\,d\mathcal{H}^{n}(x), \tag*{(1)} E [ W ] = ∫ Ω × 0 H 0 ( ∂ ∘ W ∩ π − 1 ( x ) ) d L n ( x ) = ∫ ∂ ∘ W ∣ ⟨ v , n ( x )⟩ ∣ d H n ( x ) , (1)
where n ( x ) \boldsymbol{n}(x) n ( x ) is the unit normal vector to the approximate tangent space Tan n ( ∂ ∗ W , x ) \operatorname{Tan}^{n}(\partial^{*}W,x) Tan n ( ∂ ∗ W , x ) (which coincides with the usual tangent space where ∂ ∗ W \partial^{*}W ∂ ∗ W is smooth), v = ( 0 , … , 0 , 1 ) \boldsymbol{v}=(0,\ldots,0,1) v = ( 0 , … , 0 , 1 ) , L n \mathcal{L}^{n} L n is the Lebesgue measure, and H n \mathcal{H}^{n} H n is the Hausdorff measure. The equality of the two expressions above follows from the area formula (see [13, Remark 2.94] or [14, 3.2.22]).
Definition 1. Let P , Q \mathcal{P},\mathcal{Q} P , Q be cell structures in Ω \Omega Ω . The one-to-one volume exchange metric is
d V 1 ( P , Q ) = min W ∈ F 1 ( P , Q ) E [ W ] d_{\mathrm{V}}^{1}(\mathcal{P},\mathcal{Q})=\min_{W\in\mathcal{F}^{1}(\mathcal{P},\mathcal{Q})}\mathcal{E}[W] d V 1 ( P , Q ) = W ∈ F 1 ( P , Q ) min E [ W ] and the many-to-many volume exchange dissimilarity is
d V 2 ( P , Q ) = min W ∈ F 2 ( P , Q ) E [ W ] . d_{\mathrm{V}}^{2}(\mathcal{P},\mathcal{Q})=\min_{W\in\mathcal{F}^{2}(\mathcal{P},\mathcal{Q})}\mathcal{E}[W]. d V 2 ( P , Q ) = W ∈ F 2 ( P , Q ) min E [ W ] .
The existence of these minima will be shown in Proposition 24 below as a corollary of our main theorem.
We now define discrete analogues of the two volume exchange metrics.
Definition 2. A partial matching between two sets P \mathcal{P} P and Q \mathcal{Q} Q is a subset R \mathcal{R} R of ( P ∪ { ∗ } ) × ( Q ∪ { ∗ } ) (\mathcal{P}\cup\{\ast\})\times(\mathcal{Q}\cup\{\ast\}) ( P ∪ { ∗ }) × ( Q ∪ { ∗ }) such that each cell of P \mathcal{P} P is matched to exactly one element of ( Q ∪ { ∗ } ) (\mathcal{Q}\cup\{\ast\}) ( Q ∪ { ∗ }) and each cell of Q \mathcal{Q} Q is matched to exactly one element of ( P ∪ { ∗ } ) (\mathcal{P}\cup\{\ast\}) ( P ∪ { ∗ }) .
We denote the collection of partial matchings between P \mathcal{P} P and Q \mathcal{Q} Q as PM ( P , Q ) \operatorname{PM}(\mathcal{P},\mathcal{Q}) PM ( P , Q ) .
See Figure 4 . Note that PM ( P , Q ) = PM ( Q , P ) \operatorname{PM}(\mathcal{P},\mathcal{Q})=\operatorname{PM}(\mathcal{Q},\mathcal{P}) PM ( P , Q ) = PM ( Q , P ) .
Figure 4. The optimal partial matching between the cell structures in the top row is illustrated by the colors in the bottom row. That is, the dark blue, orange, and green cells are matched with each other, whereas the pink, light blue, yellow, and red cells are matched to ∗ \ast ∗ . The cost of the matching is the area of the shaded region on the right. The optimal independent matching would also pair the yellow cell with the green cell, reducing the cost by the area of the former.
Definition 3. An independent matching between P \mathcal{P} P and Q \mathcal{Q} Q is a partial matching between coarsenings of P \mathcal{P} P and Q \mathcal{Q} Q .
For cell structures P , Q ⊂ Ω \mathcal{P},\mathcal{Q}\subset\Omega P , Q ⊂ Ω denote by PM ( P , Q ) \operatorname{PM}(\mathcal{P},\mathcal{Q}) PM ( P , Q ) the collection of partial matchings between the cells of P \mathcal{P} P and Q \mathcal{Q} Q and by IM ( P , Q ) \operatorname{IM}(\mathcal{P},\mathcal{Q}) IM ( P , Q ) the collection of independent matchings of the cells of P \mathcal{P} P and Q \mathcal{Q} Q .
Definition 4. Let P , Q \mathcal{P},\mathcal{Q} P , Q be cell structures in Ω \Omega Ω . The one-to-one discrete volume exchange metric between P \mathcal{P} P and Q \mathcal{Q} Q is defined as
d D V 1 ( P , Q ) : = 1 2 min R ∈ PM ( P , Q ) ∑ ( E , F ) ∈ R L n ( E △ F ) (2) d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q}) := \frac{1}{2}\min_{\mathcal{R}\in\operatorname{PM}(\mathcal{P},\mathcal{Q})}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^{n}(E\mathbin{\triangle}F) \tag*{(2)} d DV 1 ( P , Q ) := 2 1 R ∈ PM ( P , Q ) min ( E , F ) ∈ R ∑ L n ( E △ F ) (2) where E △ F : = ( E ∖ F ) ∪ ( F ∖ E ) E\mathbin{\triangle}F:=(E\setminus F)\cup(F\setminus E) E △ F := ( E ∖ F ) ∪ ( F ∖ E ) denotes the symmetric difference between sets E E E and $F and we treat ∗ \ast ∗ as the empty set. Similarly, the many-to-many discrete volume exchange dissimilarity is
d D V 2 ( P , Q ) : = 1 2 min R ∈ IM ( P , Q ) ∑ ( E ′ , F ′ ) ∈ R L n ( E ′ △ F ′ ) (3) d_{\mathrm{DV}}^{2}(\mathcal{P},\mathcal{Q}) := \frac{1}{2}\min_{\mathcal{R}\in\operatorname{IM}(\mathcal{P},\mathcal{Q})}\sum_{(E',F')\in\mathcal{R}}\mathcal{L}^{n}(E'\mathbin{\triangle}F') \tag*{(3)} d DV 2 ( P , Q ) := 2 1 R ∈ IM ( P , Q ) min ( E ′ , F ′ ) ∈ R ∑ L n ( E ′ △ F ′ ) (3)
We show that the minima are attained when P \mathcal{P} P and Q \mathcal{Q} Q have countably many cells in Proposition 24. As we explain below, d D V 1 ( P , Q ) d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q}) d DV 1 ( P , Q ) can be computed efficiently by converting to an equivalent linear assignment problem.
Our main theorem is the equality of the continuous and discrete volume exchange metrics.
Theorem 5. Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^{n} R n and let P , Q \mathcal{P},\mathcal{Q} P , Q be cell structures in Ω \Omega Ω . Then
d V 1 ( P , Q ) = d D V 1 ( P , Q ) d_{\mathrm{V}}^{1}(\mathcal{P},\mathcal{Q})=d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q}) d V 1 ( P , Q ) = d DV 1 ( P , Q ) and
d V 2 ( P , Q ) = d D V 2 ( P , Q ) . d_{\mathrm{V}}^{2}(\mathcal{P},\mathcal{Q})=d_{\mathrm{DV}}^{2}(\mathcal{P},\mathcal{Q}). d V 2 ( P , Q ) = d DV 2 ( P , Q ) .
The proof of Theorem 5 relies heavily upon the tools of geometric measure theory, a field that arose from the study of Plateau’s problem on minimal surfaces and its generalizations. Towards that end, we convert the statement into one concerning a distance between piecewise-constant functions, where a piecewise-constant function is one whose non-empty level sets form the cells of a cell structure. Note that the assignment of labels in a metric space ( Y , δ ) (Y,\delta) ( Y , δ ) to the cells of a cell structure P \mathcal{P} P induces to a piecewise-constant function p : Ω → Y p:\Omega\to Y p : Ω → Y , which is well-defined up to a set of Lebesgue measure zero. Given a partial matching R \mathcal{R} R between the cells of P \mathcal{P} P and those of Q \mathcal{Q} Q , we may choose Y Y Y to be a discrete metric space and label the cells of P \mathcal{P} P and Q \mathcal{Q} Q so that matched cells have the same labels. In Lemma 23 we show
1 2 ∑ ( E , F ) ∈ R L n ( E △ F ) = ∫ Ω δ ( p , q ) d L n . \frac{1}{2}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^{n}(E\mathbin{\triangle}F)=\int_{\Omega}\delta(p,q)\,\mathrm{d}\mathcal{L}^{n}. 2 1 ( E , F ) ∈ R ∑ L n ( E △ F ) = ∫ Ω δ ( p , q ) d L n .
On the other hand, given two piecewise-constant functions p : Ω → Y p:\Omega\to Y p : Ω → Y and q : Ω → Y q:\Omega\to Y q : Ω → Y , a piecewise-constant filling between p p p and q q q is a piecewise-constant function w : Ω × ( 0 , 1 ) → Y w:\Omega\times(0,1)\to Y w : Ω × ( 0 , 1 ) → Y so that the boundary trace (the “approximate limits” of w w w on the boundary) satisfy w ∣ Ω × 0 = p w|_{\Omega\times0}=p w ∣ Ω × 0 = p and w ∣ Ω × 1 = q w|_{\Omega\times1}=q w ∣ Ω × 1 = q , taken up to equivalence in the L 1 L^{1} L 1 norm. There is a correspondence between Y Y Y -labeled cellular fillings between P \mathcal{P} P and Q \mathcal{Q} Q and piecewise-constant fillings between functions p p p and q q q which are constant on the grains of P \mathcal{P} P and Q \mathcal{Q} Q respectively. We define the energy of w w w as follows. We may write Ω × ( 0 , 1 ) = C ∪ S ∪ F \Omega\times(0,1)=C\cup S\cup F Ω × ( 0 , 1 ) = C ∪ S ∪ F where w w w is asymptotically almost everywhere constant in small neighborhoods of points in C C C , where w w w takes two values w + ( x ) w^{+}(x) w + ( x ) and w − ( x ) w^{-}(x) w − ( x ) asymptotically almost everywhere in small neighborhoods of x ∈ S x \in S x ∈ S , and H n ( F ) = 0 \mathcal{H}^n(F) = 0 H n ( F ) = 0 . Furthermore, S S S is H n \mathcal{H}^n H n -rectifiable with a well-defined approximate unit normal n w : S → S n n_w:S \to\mathbb{S}^n n w : S → S n . We define the projected surface energy of w w w as
E δ [ w ] = ∫ S δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n (4) \mathcal{E}_{\delta}[w] = \int_S \delta(w^+,w^-)\lvert\langle v,n_w\rangle\rvert\,d\mathcal{H}^n \tag*{(4)} E δ [ w ] = ∫ S δ ( w + , w − ) ∣⟨ v , n w ⟩∣ d H n (4)
where v = ( 0 , … , 0 , 1 ) v=(0,\ldots,0,1) v = ( 0 , … , 0 , 1 ) is the unit vector in the “vertical” direction.
Theorem 6. Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^n R n and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete, separable metric space. For any two piecewise constant functions p , q ∈ PC ( Ω ; Y ) p,q \in\operatorname{PC}(\Omega;Y) p , q ∈ PC ( Ω ; Y ) on Ω \Omega Ω ,
min w ∈ F ( p , q ) E δ [ w ] = ∫ Ω δ ( p , q ) d L n \min_{w\in\mathrm{F}(p,q)}\mathcal{E}_{\delta}[w] = \int_{\Omega}\delta(p,q)\,d\mathcal{L}^n w ∈ F ( p , q ) min E δ [ w ] = ∫ Ω δ ( p , q ) d L n and the minimum exists, where F ( p , q ) \mathrm{F}(p,q) F ( p , q ) denotes the collection of piecewise-constant fillings between p p p and $q.
Outline
We begin in Section 2 by reviewing concepts from metric geometry and geometric measure theory including the properties of scalar-valued functions of bounded variation (BV) and sets of finite perimeter. Section 3 develops the theory of metric space valued BV functions, with the beginning and Section 3.3 reviewing the concept of an approximate limits [15] and defining the terms appearing in Equations 1 and 4. A key technical result is Theorem 13 in Section 3.2, which states that if ( Y , δ ) (Y,\delta) ( Y , δ ) is a complete, separable metric space, Ω \Omega Ω is a bounded, open, connected subset of R n \mathbb{R}^n R n , and p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y are BV functions then
min w ∈ BV ( Ω × I ; Y ) w ∣ Ω × 0 = p a . e . w ∣ Ω × 1 = q a . e . ∫ Ω ∣ D w x ∣ ( 0 , 1 ) d L n ( x ) = ∫ Ω δ ( p , q ) d L n . \min_{\substack{w\in\operatorname{BV}(\Omega\times I;Y)\\ w|_{\Omega\times0}=p\ \mathrm{a.e.}\\ w|_{\Omega\times1}=q\ \mathrm{a.e.}}}\int_{\Omega}\lvert D w_x\rvert(0,1)\,d\mathcal{L}^n(x)=\int_{\Omega}\delta(p,q)\,d\mathcal{L}^n. w ∈ BV ( Ω × I ; Y ) w ∣ Ω × 0 = p a.e. w ∣ Ω × 1 = q a.e. min ∫ Ω ∣ D w x ∣ ( 0 , 1 ) d L n ( x ) = ∫ Ω δ ( p , q ) d L n .
In the special case where w w w is a piecewise-constant filling between p p p and q q q , the infimand on the left hand side agrees with the projected surface area defined in (4) . As such, this is a key step towards proving Theorems 6 and 5. Theorem 13 is proven by first showing that the projected surface area of w w w is bounded below by the integral of the total variation of one-dimensional slices w x ( t ) = w ( x , t ) w_x(t)=w(x,t) w x ( t ) = w ( x , t ) which is in turn bounded by the L 1 L^1 L 1 distance between p p p and q q q . Then, this lower bound is achieved by the filling w 0 : Ω × I → Y w_0:\Omega\times I\to Y w 0 : Ω × I → Y defined by
w 0 ( x , t ) = { p ( x ) t ≤ 1 / 2 , q ( x ) t > 1 / 2. w_0(x,t)=
\begin{cases}
p(x) & t\leq1/2,\\
q(x) & t>1/2.
\end{cases} w 0 ( x , t ) = { p ( x ) q ( x ) t ≤ 1/2 , t > 1/2.
Note that if p , q p,q p , q are piecewise constant then so is w 0 w_0 w 0 .
Three types of piecewise constant fillings between piecewise constant functions are defined in Section 4. These lead to versions of the one-to-one volume exchange metric and many-to-many volume exchange dissimilarity in this setting, which are shown to agree with the notions in the introduction in Proposition 22. This section also includes a proof of Theorem 6.
Section 5 begins with a proof of the main result of the paper, Theorem 5. Next, the metric properties of the one-to-one volume exchange metric and many-to-many volume exchange dissimilarity are explored in Section 5.1. Sections 5.2 and 5.3 explain how a dual formulation of the discrete one-to-one volume exchange metric can be computed efficiently as a linear assignment problem and Section 5.4 outlines an algorithm to compute the many-to-many volume exchange dissimilarity.
Finally, Section 6 describes computational experiments applying these dissimilarities to a dataset of synthetic microstructures.
Mathematical Preliminaries
In this section, we will review this material and provide references. Most of the material in this section can be found in Ambrosio, Fusco, and Pallara’s monograph [13] on functions of bounded variation, or Maggi’s book [16] on sets of finite perimeter.
We will use these properties to show that the one-to-one discrete volume exchange is in fact a metric. Whenever δ \delta δ satisfies symmetry, non-negativity, and δ ( y , y ) = 0 \delta(y,y)=0 δ ( y , y ) = 0 for all y ∈ Y y \in Y y ∈ Y , our function δ \delta δ is called a dissimilarity .
A metric space is a set Y Y Y together with a distance (metric) δ \delta δ , a symmetric real-valued function defined on Y × Y Y \times Y Y × Y such that δ ( y 1 , y 2 ) = 0 \delta(y_1,y_2)=0 δ ( y 1 , y 2 ) = 0 if and only if y 1 = y 2 y_1=y_2 y 1 = y 2 , and δ ( y 1 , y 2 ) ≤ δ ( y 1 , y 3 ) + δ ( y 3 , y 2 ) \delta(y_1,y_2) \le\delta(y_1,y_3)+\delta(y_3,y_2) δ ( y 1 , y 2 ) ≤ δ ( y 1 , y 3 ) + δ ( y 3 , y 2 ) for all y 1 , y 2 , y 3 ∈ Y y_1,y_2,y_3 \in Y y 1 , y 2 , y 3 ∈ Y . A function φ : Y → Z \varphi:Y \to Z φ : Y → Z from the metric space Y Y Y into another metric space ( Z , d Z ) (Z,d_Z) ( Z , d Z ) is called distance preserving if
d Z ( φ ( y ) , φ ( y ′ ) ) = δ ( y , y ′ ) for all y , y ′ ∈ Y . (5) d_Z(\varphi(y),\varphi(y'))=\delta(y,y') \qquad\text{for all } y,y' \in Y. \tag*{(5)} d Z ( φ ( y ) , φ ( y ′ )) = δ ( y , y ′ ) for all y , y ′ ∈ Y . (5)
If in addition, φ \varphi φ is surjective (and hence bijective) we call φ \varphi φ an isometry , and say that Y Y Y and Z Z Z are isometric . The collection of all isometries from Y Y Y to Z Z Z is denoted by Iso ( Y ; Z ) \operatorname{Iso}(Y;Z) Iso ( Y ; Z ) ; when Z = Y Z=Y Z = Y we write Iso ( Y ) \operatorname{Iso}(Y) Iso ( Y ) as opposed to Iso ( Y ; Y ) \operatorname{Iso}(Y;Y) Iso ( Y ; Y ) .
Let us go through some terminology and notations from measure theory and scalar-valued functions of bounded variation (BV-functions) that we will liberally use throughout the paper. We refer the reader to [13] for a thorough treatment of these topics.
We let B ( R n ) \mathcal{B}(\mathbb{R}^n) B ( R n ) denote the Borel σ \sigma σ -algebra of R n \mathbb{R}^n R n , the smallest σ \sigma σ -algebra on R n \mathbb{R}^n R n containing all of the open sets. A Borel measure is a σ \sigma σ -additive set function μ : B ( R n ) → [ 0 , + ∞ ] \mu:\mathcal{B}(\mathbb{R}^n) \to[0,+\infty] μ : B ( R n ) → [ 0 , + ∞ ] such that μ ( ∅ ) = 0 \mu(\varnothing)=0 μ ( ∅ ) = 0 . If in addition, μ ( R n ) < ∞ \mu(\mathbb{R}^n)<\infty μ ( R n ) < ∞ , then μ \mu μ is called a finite Borel measure . If a positive Borel measure μ \mu μ is finite on compact sets, it is called a Radon measure . Similarly, an σ \sigma σ -additive set function μ : B ( R n ) → R m \mu:\mathcal{B}(\mathbb{R}^n) \to\mathbb{R}^m μ : B ( R n ) → R m (with μ ( ∅ ) = 0 \mu(\varnothing)=0 μ ( ∅ ) = 0 ) is called a vector measure on R n \mathbb{R}^n R n . We let M ( R n ; R m ) \mathcal{M}(\mathbb{R}^n;\mathbb{R}^m) M ( R n ; R m ) denote the collection of all vector (R m \mathbb{R}^m R m -valued) measures in R n \mathbb{R}^n R n . The total variation ∣ μ ∣ |\mu| ∣ μ ∣ of μ \mu μ is defined by ∣ μ ∣ ( B ) : = sup ∑ k = 1 ∞ ∣ μ ( B k ) ∣ |\mu|(B):=\sup\sum_{k=1}^{\infty}|\mu(B_k)| ∣ μ ∣ ( B ) := sup ∑ k = 1 ∞ ∣ μ ( B k ) ∣ , where the supremum is taken over all partitions { B k } \{B_k\} { B k } of B B B such that each B k B_k B k is a Borel set. Importantly, for any μ ∈ M ( R n ; R m ) \mu\in\mathcal{M}(\mathbb{R}^n;\mathbb{R}^m) μ ∈ M ( R n ; R m ) , μ ( ∅ ) = 0 \mu(\varnothing)=0 μ ( ∅ ) = 0 and its total variation ∣ μ ∣ |\mu| ∣ μ ∣ is a finite Borel measure on R n \mathbb{R}^n R n .
We will often use of the n n n -dimensional Lebesgue measure L n \mathcal{L}^n L n in R n \mathbb{R}^n R n , the k k k -dimensional Hausdorff measure H k \mathcal{H}^k H k , and frequently, the Hausdorff measure \mathcal{H}^k \mathbin{\vrule height 1.4ex depth -0.4ex width 0.07ex\vrule height 0.07ex depth -0.02ex width 0.8ex} \Sigma restricted to “well-behaved” subsets Σ \Sigma Σ of R n \mathbb{R}^n R n , defined as follows. For any measure μ \mu μ and Borel set E E E in R n \mathbb{R}^n R n , we define a Borel measure \mu\mathbin{\vrule height 1.4ex depth -0.4ex width 0.07ex\vrule height 0.07ex depth -0.02ex width 0.8ex}E(A):=\mu(E \cap A) , for any Borel set A ⊂ R n A \subset\mathbb{R}^n A ⊂ R n .
Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^n R n . We let L 1 ( Ω ) L^1(\Omega) L 1 ( Ω ) denote the collection of all L n \mathcal{L}^n L n -measurable, real-valued functions f f f on Ω \Omega Ω with finite L 1 L^1 L 1 -norm: ∥ f ∥ L 1 ( Ω ) : = ∫ Ω ∣ f ∣ d L n < + ∞ \|f\|_{L^1(\Omega)}:=\int_{\Omega}|f|\,d\mathcal{L}^n<+\infty ∥ f ∥ L 1 ( Ω ) := ∫ Ω ∣ f ∣ d L n < + ∞ . We let \fint_A f\,d\mu denote the average 1 μ ( A ) ∫ A f d μ \frac{1}{\mu(A)}\int_A f\,d\mu μ ( A ) 1 ∫ A f d μ . We turn L 1 ( Ω ) L^1(\Omega) L 1 ( Ω ) into a metric space by identifying two functions together when the L 1 L^1 L 1 -norm of their difference is zero; equivalently, when the two functions differ on a set of L n \mathcal{L}^n L n -measure zero. If for each j = 1 , … , n j=1,\ldots,n j = 1 , … , n , there exists a signed finite Radon measure D j f D_jf D j f in Ω \Omega Ω satisfying
∫ Ω f ∂ j ϕ d L n = − ∫ Ω ϕ d D j f for all ϕ ∈ C c ∞ ( Ω ) , (6) \int_{\Omega} f\,\partial_j\phi\,d\mathcal{L}^n=-\int_{\Omega}\phi\,dD_jf \qquad\text{for all } \phi\in C_c^\infty(\Omega), \tag*{(6)} ∫ Ω f ∂ j ϕ d L n = − ∫ Ω ϕ d D j f for all ϕ ∈ C c ∞ ( Ω ) , (6)
then f f f is called a BV-function on Ω \Omega Ω , the vector-valued measure D f = ( D 1 f , … , D n f ) Df = (D_1f,\ldots,D_nf) D f = ( D 1 f , … , D n f ) the weak-derivative of f f f , and D j f D_jf D j f , the weak-derivative of f f f in the j j j -th (or e j e_j e j -th) direction. We denote the set of all BV-functions in Ω \Omega Ω by BV ( Ω ) \operatorname{BV}(\Omega) BV ( Ω ) .
A subset S S S of R n + 1 \mathbb{R}^{n+1} R n + 1 is called countably H n \mathcal{H}^n H n -rectifiable if S S S is contained in the union of (at most) countably many images of Lipschitz functions from R n \mathbb{R}^n R n to R n + 1 \mathbb{R}^{n+1} R n + 1 , up to an H n \mathcal{H}^n H n -negligible set. For H n \mathcal{H}^n H n -a.e. x ∈ S x\in S x ∈ S there exists an n n n -dimensional (vector) subspace V ⊆ R n + 1 V\subseteq\mathbb{R}^{n+1} V ⊆ R n + 1 called the approximate tangent space of S S S at x x x , the n n n -dimensional subspace V V V of R n + 1 \mathbb{R}^{n+1} R n + 1 such that
lim r → 0 ∫ S x , r ϕ d H n = ∫ V ϕ d H n for all ϕ ∈ C c ( R n + 1 ; R ) , (7) \lim_{r\to0}\int_{S_{x,r}}\phi\,d\mathcal{H}^n=\int_V\phi\,d\mathcal{H}^n\quad\text{for all }\phi\in C_c(\mathbb{R}^{n+1};\mathbb{R}), \tag*{(7)} r → 0 lim ∫ S x , r ϕ d H n = ∫ V ϕ d H n for all ϕ ∈ C c ( R n + 1 ; R ) , (7)
where S x , r = ( S − x ) / r S_{x,r}=(S-x)/r S x , r = ( S − x ) / r for any x ∈ S x\in S x ∈ S and r > 0 r>0 r > 0 , and denoted by Tan n ( S , x ) \operatorname{Tan}^n(S,x) Tan n ( S , x ) .
If S S S is a countably H n \mathcal{H}^n H n -rectifiable subset of R n + 1 \mathbb{R}^{n+1} R n + 1 , we say that S S S is oriented by a Borel map n : S → S n \boldsymbol{n}:S\to\mathbb{S}^n n : S → S n if Tan n ( S , x ) = n ⊥ ( x ) \operatorname{Tan}^n(S,x)=\boldsymbol{n}^{\perp}(x) Tan n ( S , x ) = n ⊥ ( x ) for H n \mathcal{H}^n H n -a.e. x ∈ S x\in S x ∈ S .
Sets of finite perimeter
For any L n \mathcal{L}^n L n -measurable subset E E E of R n \mathbb{R}^n R n the perimeter of E E E in Ω \Omega Ω is denoted by P ( E ; Ω ) P(E;\Omega) P ( E ; Ω ) and defined as
P ( E ; Ω ) : = sup { ∫ E div φ d x : φ ∈ C c 1 ( Ω ; R n ) , ∥ φ ∥ ∞ ≤ 1 } . P(E;\Omega):=\sup\left\{\int_E\operatorname{div}\varphi\,dx:\varphi\in C_c^1(\Omega;\mathbb{R}^n),\ \|\varphi\|_\infty\leq1\right\}. P ( E ; Ω ) := sup { ∫ E div φ d x : φ ∈ C c 1 ( Ω ; R n ) , ∥ φ ∥ ∞ ≤ 1 } .
Remark 7. The class of sets of finite perimeter in Ω \Omega Ω includes all sets E E E with C 1 C^1 C 1 boundary inside Ω \Omega Ω such that H n − 1 ( Ω ∩ ∂ E ) < ∞ \mathcal{H}^{n-1}(\Omega\cap\partial E)<\infty H n − 1 ( Ω ∩ ∂ E ) < ∞ . For such sets, H n − 1 ( Ω ∩ ∂ E ) = P ( E , Ω ) \mathcal{H}^{n-1}(\Omega\cap\partial E)=P(E,\Omega) H n − 1 ( Ω ∩ ∂ E ) = P ( E , Ω ) .
We will now review a few notions of measure theoretic ways of capturing the boundary, interior, and exterior for a set of finite perimeter. The reduced boundary of a set of finite perimeter E E E in R n \mathbb{R}^n R n is the collection ∂ ∗ E \partial_*E ∂ ∗ E of all points x ∈ R n x\in\mathbb{R}^n x ∈ R n such that the limit
n E ( x ) : = lim r → 0 + D χ E ( B ( x , r ) ) ∣ D χ E ∣ ( B ( x , r ) ) \boldsymbol{n}_E(x):=\lim_{r\to0+}\frac{D\chi_E(B(x,r))}{|D\chi_E|(B(x,r))} n E ( x ) := r → 0 + lim ∣ D χ E ∣ ( B ( x , r )) D χ E ( B ( x , r ))
exists in R n \mathbb{R}^n R n and satisfies ∣ n E ( x ) ∣ = 1 |\boldsymbol{n}_E(x)|=1 ∣ n E ( x ) ∣ = 1 . For each t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , we let E ( t ) E^{(t)} E ( t ) denote the collection of all points x ∈ R n x\in\mathbb{R}^n x ∈ R n of density t t t , i.e.,
E ( t ) : = { x ∈ R n : lim r → 0 + L n ( E ∩ B ( x , r ) ) L n ( B ( x , r ) ) = t } . (8) E^{(t)}:=\left\{x\in\mathbb{R}^n:\lim_{r\to0+}\frac{\mathcal{L}^n(E\cap B(x,r))}{\mathcal{L}^n(B(x,r))}=t\right\}. \tag*{(8)} E ( t ) := { x ∈ R n : r → 0 + lim L n ( B ( x , r )) L n ( E ∩ B ( x , r )) = t } . (8)
We call E ( 1 ) E^{(1)} E ( 1 ) the measure theoretic interior , and E ( 0 ) E^{(0)} E ( 0 ) the measure theoretic exterior , and the set ∂ ∗ E : = R n ∖ ( E ( 0 ) ∪ E ( 1 ) ) \partial^*E:=\mathbb{R}^n\setminus(E^{(0)}\cup E^{(1)}) ∂ ∗ E := R n ∖ ( E ( 0 ) ∪ E ( 1 ) ) the essential boundary of E E E . Federer showed (see [13, Theorem 3.61]) that
∂ ∗ E ⊂ E ( 1 / 2 ) ⊂ ∂ ∗ E ⊂ N ∪ ∂ ∗ E \partial_*E\subset E^{(1/2)}\subset\partial^*E\subset N\cup\partial_*E ∂ ∗ E ⊂ E ( 1/2 ) ⊂ ∂ ∗ E ⊂ N ∪ ∂ ∗ E
for some H n − 1 \mathcal{H}^{n-1} H n − 1 -negligible N ⊂ R n N\subset\mathbb{R}^n N ⊂ R n .
Definition 8. A Caccioppoli partition of Ω \Omega Ω indexed by I ⊂ N I\subset\mathbb{N} I ⊂ N is a partition E = { E i } i ∈ I \mathcal{E}=\{E_i\}_{i\in I} E = { E i } i ∈ I of Ω \Omega Ω such that ∑ i ∈ I P ( E i , Ω ) < ∞ \sum_{i\in I}P(E_i,\Omega)<\infty ∑ i ∈ I P ( E i , Ω ) < ∞ . We assume that ∣ E i ∣ > 0 |E_i|>0 ∣ E i ∣ > 0 for all i ∈ I i\in I i ∈ I and consider two partitions to be identical up to re-ordering of the indices or the redistribution of sets of measure zero.
Metric Space Valued BV Functions
Throughout this section (unless otherwise stated) we let Ω \Omega Ω be a bounded, connected, open set in R n \mathbb{R}^{n} R n , we let I = ( 0 , 1 ) I=(0,1) I = ( 0 , 1 ) , and we let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete, separable metric space. Recall from the introduction that the surface energy of a piecewise-constant filling w w w from Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) into Y Y Y is
E δ [ w ] = ∫ S δ ( w + , w − ) ∣ ⟨ v , n ⟩ ∣ d H n \mathcal{E}_{\delta}[w]=\int_{S}\delta(w^{+},w^{-})\lvert\langle v,n\rangle\rvert\,d\mathcal{H}^{n} E δ [ w ] = ∫ S δ ( w + , w − ) ∣⟨ v , n ⟩∣ d H n
where S S S is a set consisting of points x 0 x_{0} x 0 so that w w w limits to two values w + ( x ) w^{+}(x) w + ( x ) , w − ( x ) w^{-}(x) w − ( x ) in sufficiently small neighborhoods of x x x . A major goal of this section is to show in Theorem 16 that this expression is well-defined for a class of metric space valued BV functions . This strengthens an earlier result by Ambrosio [15] which required the metric space Y Y Y to be separable and proper. Later, we will apply this theorem to a countable discrete metric space which is not proper.
Before we begin Section 3.1, we review notions of approximate limit, one-sided trace, boundary trace, and define our notion of a metric space valued BV function, first introduced by Ambrosio in [15]. Afterwards, we show a version of the Lebesgue differentiation theorem for functions in L l o c 1 ( Ω ; Y ) L^{1}_{\mathrm{loc}}(\Omega;Y) L loc 1 ( Ω ; Y ) , the class of all measurable functions f : Ω → Y f:\Omega\to Y f : Ω → Y such that every point of Ω \Omega Ω has an open neighborhood U ⊂ Ω U\subset\Omega U ⊂ Ω satisfying
∫ U δ ( f , y 0 ) d L n < + ∞ \int_{U}\delta(f,y_{0})\,d\mathcal{L}^{n}<+\infty ∫ U δ ( f , y 0 ) d L n < + ∞
for some y 0 ∈ Y y_{0}\in Y y 0 ∈ Y . The class of functions for which U U U can be taken to be Ω \Omega Ω is denoted by L 1 ( Ω ; Y ) L^{1}(\Omega;Y) L 1 ( Ω ; Y ) . We include a proof of this fact as an introduction to the arguments we frequently use in §3 and §4. In Section 3.1, we show that the boundary trace of a metric space valued BV function f f f on Ω × ( 0 , 1 ) \Omega\times(0,1) Ω × ( 0 , 1 ) agrees with those of the vertical restriction f x = f ( x , ⋅ ) f_{x}=f(x,\cdot) f x = f ( x , ⋅ ) for almost every x ∈ Ω x\in\Omega x ∈ Ω . This is applied in Section 3.2 to prove the second major result of this section, Theorem 13. As described in the outline, this is a major step towards proving the main theorems of the paper. Finally, Section 3.3 includes a proof of Theorem 16 which was discussed in the preceding paragraph.
We mostly use the same definitions as in Ambrosio’s seminal work on metric space valued BV functions [15], but slightly differ on the notion of an approximate limit . We say that a Borel function w : Ω → Y w:\Omega\to Y w : Ω → Y has an approximate limit at x 0 ∈ Ω x_{0}\in\Omega x 0 ∈ Ω if there exists a y 0 ∈ Y y_{0}\in Y y 0 ∈ Y such that
\lim_{r\to0+}\fint_{\Omega\cap B(x_{0},r)}\delta(w,y_{0})\,d\mathcal{L}^{n}=0. \tag*{(9)}
If the approximate limit y 0 y_{0} y 0 exists, it is unique, and will be denoted by a p l i m x → x 0 w ( x ) \mathop{\mathrm{ap\,lim}}_{x\to x_{0}}w(x) ap lim x → x 0 w ( x ) . The Borel set S w S_{w} S w of points in Ω \Omega Ω where w w w does not satisfy condition (9) is called the approximate discontinuity set . Whenever the limit (9) holds for a point x 0 ∈ ∂ Ω x_{0}\in\partial\Omega x 0 ∈ ∂ Ω , we call y 0 y_{0} y 0 the boundary trace of w w w at x 0 x_{0} x 0 .
If the boundary trace of w w w exists for H n − 1 \mathcal{H}^{n-1} H n − 1 -a.e. x 0 ∈ Σ ⊂ ∂ Ω x_{0}\in\Sigma\subset\partial\Omega x 0 ∈ Σ ⊂ ∂ Ω , we let w ∣ Σ w|_{\Sigma} w ∣ Σ denote the function w ∣ Σ ( x 0 ) = a p l i m x → x 0 w ( x ) w|_{\Sigma}(x_{0})=\mathop{\mathrm{ap\,lim}}_{x\to x_{0}}w(x) w ∣ Σ ( x 0 ) = ap lim x → x 0 w ( x ) .
A variation to the notion of an approximate limit is that of a one-sided trace, and a boundary trace. For a fixed unit vector n ∈ S n − 1 n\in S^{n-1} n ∈ S n − 1 we say that a 0 ∈ Y a_{0}\in Y a 0 ∈ Y is the positive one-sided trace of w w w and b 0 ∈ Y b_{0}\in Y b 0 ∈ Y is the negative one-sided trace of w w w if
\begin{aligned}
\lim_{r\to0+}\fint_{\Omega\cap B^{+}_{n}(x_{0},r)}\delta(w,a_{0})\,d\mathcal{L}^{n}&=0
\quad\text{and}\quad
\lim_{r\to0+}\fint_{\Omega\cap B^{-}_{n}(x_{0},r)}\delta(w,b_{0})\,d\mathcal{L}^{n}=0.
\end{aligned}
where B n + ( x 0 , r ) : = B ( x 0 , r ) ∩ H n + B_n^+(x_0,r):=B(x_0,r)\cap H_n^+ B n + ( x 0 , r ) := B ( x 0 , r ) ∩ H n + and B n − ( x 0 , r ) = B ( x 0 , r ) ∩ H n − B_n^-(x_0,r)=B(x_0,r)\cap H_n^- B n − ( x 0 , r ) = B ( x 0 , r ) ∩ H n − are the two (open) halves of the ball B ( x 0 , r ) B(x_0,r) B ( x 0 , r ) defined by its intersection with the open half-spaces H n + : = { x : ⟨ x − x 0 , n ⟩ > 0 } H_n^+:=\{x:\langle x-x_0,n\rangle>0\} H n + := { x : ⟨ x − x 0 , n ⟩ > 0 } and H n − : = { x : ⟨ x − x 0 , n ⟩ < 0 } H_n^-:=\{x:\langle x-x_0,n\rangle<0\} H n − := { x : ⟨ x − x 0 , n ⟩ < 0 } .
Whenever a one-sided trace of w w w exists at x 0 x_0 x 0 , we denote it by w ± ( x 0 , n ) w^\pm(x_0,n) w ± ( x 0 , n ) .
A Borel function w : Ω → Y w:\Omega\to Y w : Ω → Y such that δ ( w , y 0 ) ∈ L 1 ( Ω ; R ) \delta(w,y_0)\in L^1(\Omega;\mathbb{R}) δ ( w , y 0 ) ∈ L 1 ( Ω ; R ) for some y 0 ∈ Y y_0\in Y y 0 ∈ Y is said to be a Y Y Y -valued function of bounded variation (or a metric B V BV B V function ) if there exists a finite, positive measure σ \sigma σ on Ω \Omega Ω such that for any 1-Lipschitz real-valued function φ : Y → R \varphi:Y\to\mathbb{R} φ : Y → R ,
∣ D ( φ ∘ w ) ∣ ( B ) ≤ σ ( B ) for all B ∈ B ( Ω ) . (10) |D(\varphi\circ w)|(B)\leq\sigma(B)\qquad\text{for all }B\in\mathcal{B}(\Omega). \tag*{(10)} ∣ D ( φ ∘ w ) ∣ ( B ) ≤ σ ( B ) for all B ∈ B ( Ω ) . (10)
The least such measure σ \sigma σ is called the total variation of w w w and is denoted ∣ D w ∣ |Dw| ∣ D w ∣ . We denote the class of all Y Y Y -valued BV-function by B V ( Ω ; Y ) BV(\Omega;Y) B V ( Ω ; Y ) .
Using the separability of Y Y Y and the Lebesgue differentiation theorem for real-valued functions, we now show that the Lebesgue differentiation theorem holds for any function in L l o c 1 ( Ω ; Y ) L^1_{\mathrm{loc}}(\Omega;Y) L loc 1 ( Ω ; Y ) .
Proposition 9. Let Ω ⊂ R n \Omega\subset\mathbb{R}^n Ω ⊂ R n be open and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a separable metric space. If f ∈ L l o c 1 ( Ω ; Y ) f\in L^1_{\mathrm{loc}}(\Omega;Y) f ∈ L loc 1 ( Ω ; Y ) then
\lim_{r\to0^+}\mathop{\fint}_{\Omega\cap B(x_0,r)}\delta(f,f(x_0))\,d\mathcal{L}^n=0\qquad\text{for }\mathcal{L}^n\text{-a.e. }x_0\in\Omega.
Proof. Consider a countable dense subset { y i } \{y_i\} { y i } of Y Y Y . Since every map y ↦ δ ( y , y i ) y\mapsto\delta(y,y_i) y ↦ δ ( y , y i ) is 1-Lipschitz, the map x ↦ δ ( f ( x ) , y i ) x\mapsto\delta(f(x),y_i) x ↦ δ ( f ( x ) , y i ) is in L l o c 1 ( Ω ) L^1_{\mathrm{loc}}(\Omega) L loc 1 ( Ω ) for any i ∈ N i\in\mathbb{N} i ∈ N and hence the Lebesgue differentiation theorem applies to each of these maps. Furthermore, because { y i } \{y_i\} { y i } is countable, L n \mathcal{L}^n L n -a.e. x 0 ∈ Ω x_0\in\Omega x 0 ∈ Ω
\lim_{r\to0^+}\mathop{\fint}_{\Omega\cap B(x_0,r)}\left|\delta(f,y_i)-\delta(f(x_0),y_i)\right|\,d\mathcal{L}^n=0\qquad\text{for all }i\in\mathbb{N}. \tag*{(11)}
For any such x 0 x_0 x 0 , the triangle inequality gives us
δ ( f , f ( x 0 ) ) ≤ ∣ δ ( f , y i ) − δ ( f ( x 0 ) , y i ) ∣ + 2 δ ( f ( x 0 ) , y i ) for any i ∈ N . \delta(f,f(x_0))\leq\left|\delta(f,y_i)-\delta(f(x_0),y_i)\right|+2\delta(f(x_0),y_i)\qquad\text{for any }i\in\mathbb{N}. δ ( f , f ( x 0 )) ≤ ∣ δ ( f , y i ) − δ ( f ( x 0 ) , y i ) ∣ + 2 δ ( f ( x 0 ) , y i ) for any i ∈ N .
For any ε > 0 \varepsilon>0 ε > 0 we may choose a y i y_i y i such that δ ( f ( x 0 ) , y i ) < ε \delta(f(x_0),y_i)<\varepsilon δ ( f ( x 0 ) , y i ) < ε and therefore
\limsup_{r\to0^+}\mathop{\fint}_{\Omega\cap B(x_0,r)}\delta(f,f(x_0))\,d\mathcal{L}^n\leq2\varepsilon.
Letting ε → 0 \varepsilon\to0 ε → 0 proves the proposition. □
Boundary Traces of Vertical Restrictions
In this subsection, we investigate properties of vertical restrictions of metric BV functions on Ω × I \Omega\times I Ω × I . A vertical restriction of a function (not necessarily BV) w : Ω × I → Y w:\Omega\times I\to Y w : Ω × I → Y at x ∈ Ω x\in\Omega x ∈ Ω is the function
w x : I → Y ; w x ( t ) : = w ( x , t ) . w_x:I\to Y;\qquad w_x(t):=w(x,t). w x : I → Y ; w x ( t ) := w ( x , t ) .
We start by proving two independent lemmas for BV-curves: the endpoint (boundary) traces of BV-curves exist and their distance is bounded above by its total variation, and show in Lemma 11 that almost every restriction of a metric BV function is a BV-curve. Afterwards we show the agreement between the boundary trace of a metric BV function on the cylinder and the endpoint trace of almost every one of its vertical restrictions. We wait until §3.3 to prove the existence of boundary traces of metric BV functions.
The variation of a function γ : I → Y \gamma: I \to Y γ : I → Y , within J ⊂ I J \subset I J ⊂ I , is defined by the formula
V ( γ ; J ) = sup { ∑ i = 1 l δ ( γ ( t i ) , γ ( t i + 1 ) ) : t 1 ≤ ⋯ ≤ t l + 1 in J } . (12) \mathbf{V}(\gamma; J) = \sup\left\{ \sum_{i=1}^{l} \delta(\gamma(t_i), \gamma(t_{i+1})) : t_1 \le\cdots\le t_{l+1} \text{ in } J \right\}. \tag*{(12)} V ( γ ; J ) = sup { i = 1 ∑ l δ ( γ ( t i ) , γ ( t i + 1 )) : t 1 ≤ ⋯ ≤ t l + 1 in J } . (12)
and its essential variation , defined by
ess V ( γ ; J ) : = inf γ ^ = γ ( L ⌞ J ) -a.e. V ( γ ^ ; J ) . (13) \operatorname{ess}\mathbf{V}(\gamma; J) := \inf_{\widehat{\gamma}=\gamma\ (\mathcal{L}\llcorner J)\text{-a.e.}} \mathbf{V}(\widehat{\gamma}; J). \tag*{(13)} ess V ( γ ; J ) := γ = γ ( L └ J ) -a.e. inf V ( γ ; J ) . (13)
A function γ : I → Y \gamma: I \to Y γ : I → Y is in BV ( I ; Y ) \operatorname{BV}(I;Y) BV ( I ; Y ) if and only if ess V ( γ ; I ) < + ∞ \operatorname{ess}\mathbf{V}(\gamma; I) < +\infty ess V ( γ ; I ) < + ∞ , and moreover, ∣ D γ ∣ ( I ) = ess V ( γ ; I ) |D\gamma|(I) = \operatorname{ess}\mathbf{V}(\gamma; I) ∣ D γ ∣ ( I ) = ess V ( γ ; I ) [15]. We call any such function a BV \operatorname{BV} BV -curve in Y Y Y .
Lemma 10. If γ \gamma γ is a BV \operatorname{BV} BV -curve in a complete metric space ( Y , δ ) (Y,\delta) ( Y , δ ) , then there exist unique y 0 y_0 y 0 and y 1 y_1 y 1 in Y Y Y such that
lim r → 0 + 1 r ∫ ( 0 , r ) δ ( γ ( t ) , y 0 ) d t = 0 and lim r → 0 1 r ∫ ( 1 − r , 1 ) δ ( γ ( t ) , y 1 ) d t = 0. (14) \lim_{r\to0^+} \frac{1}{r} \int_{(0,r)} \delta(\gamma(t),y_0)\,dt = 0
\quad\text{and}\quad
\lim_{r\to0} \frac{1}{r} \int_{(1-r,1)} \delta(\gamma(t),y_1)\,dt = 0. \tag*{(14)} r → 0 + lim r 1 ∫ ( 0 , r ) δ ( γ ( t ) , y 0 ) d t = 0 and r → 0 lim r 1 ∫ ( 1 − r , 1 ) δ ( γ ( t ) , y 1 ) d t = 0. (14) Moreover, the endpoint traces satisfy
δ ( y 0 , y 1 ) ≤ ∣ D γ ∣ ( I ) . (15) \delta(y_0,y_1) \le|D\gamma|(I). \tag*{(15)} δ ( y 0 , y 1 ) ≤ ∣ D γ ∣ ( I ) . (15)
Proof. Let γ ^ \widehat{\gamma} γ be a function from I I I to Y Y Y with V ( γ ^ ; I ) < + ∞ \mathbf{V}(\widehat{\gamma}; I) < +\infty V ( γ ; I ) < + ∞ such that γ ^ = γ \widehat{\gamma} = \gamma γ = γ L \mathcal{L} L -a.e. in I I I . Assume, for the moment, its one-sided limits
lim t → 0 + γ ^ ( t ) and lim t → 1 − γ ^ ( t ) , (16) \lim_{t\to0^+} \widehat{\gamma}(t)
\quad\text{and}\quad
\lim_{t\to1^-} \widehat{\gamma}(t), \tag*{(16)} t → 0 + lim γ ( t ) and t → 1 − lim γ ( t ) , (16)
exist, and that we denote them by y 0 y_0 y 0 and y 1 y_1 y 1 , respectively. Then since one-sided traces agree with one-sided limits whenever the one-sided limits exist, the one-sided traces of γ ^ \widehat{\gamma} γ are y 0 y_0 y 0 and y 1 y_1 y 1 . Now, because γ ^ \widehat{\gamma} γ and γ \gamma γ agree L \mathcal{L} L -almost everywhere in I I I , the one-sided traces (14) of γ \gamma γ equals y 0 y_0 y 0 and y 1 y_1 y 1 . The uniqueness of the points y 0 y_0 y 0 and y 1 y_1 y 1 satisfying (14) follows from the triangle inequality.
Our only task is then to show the one-sided limits (16) exist. First, because the function t ↦ V ( γ ^ ; ( 0 , t ] ) t \mapsto\mathbf{V}(\widehat{\gamma};(0,t]) t ↦ V ( γ ; ( 0 , t ]) defined on I I I is bounded and monotonic, its one sided limits
lim t → 0 + V ( γ ^ ; ( 0 , t ] ) and lim t → 1 − V ( γ ^ ; ( 0 , t ] ) \lim_{t\to0^+} \mathbf{V}(\widehat{\gamma};(0,t])
\quad\text{and}\quad
\lim_{t\to1^-} \mathbf{V}(\widehat{\gamma};(0,t]) t → 0 + lim V ( γ ; ( 0 , t ]) and t → 1 − lim V ( γ ; ( 0 , t ])
exist. Thus, since Cauchy sequences converge in Y Y Y ,
δ ( γ ^ ( r ) , γ ^ ( t ) ) ≤ V ( γ ^ ; ( 0 , t ] ) − V ( γ ^ ; ( 0 , r ] ) for 0 < r < t < 1 , (17) \delta(\widehat{\gamma}(r),\widehat{\gamma}(t)) \le\mathbf{V}(\widehat{\gamma};(0,t]) - \mathbf{V}(\widehat{\gamma};(0,r])
\quad\text{for } 0 < r < t < 1, \tag*{(17)} δ ( γ ( r ) , γ ( t )) ≤ V ( γ ; ( 0 , t ]) − V ( γ ; ( 0 , r ]) for 0 < r < t < 1 , (17)
implies that the limits y 0 : = lim t → 0 + γ ^ ( t ) y_0 := \lim_{t\to0^+} \widehat{\gamma}(t) y 0 := lim t → 0 + γ ( t ) and y 1 : = lim t → 1 − γ ^ ( t ) y_1 := \lim_{t\to1^-} \widehat{\gamma}(t) y 1 := lim t → 1 − γ ( t ) exist.
We conclude our proof by showing inequality (15). First, inequality (17) and continuity of δ \delta δ together imply δ ( y 0 , y 1 ) ≤ V ( γ ^ ; I ) \delta(y_0,y_1) \le\mathbf{V}(\widehat{\gamma};I) δ ( y 0 , y 1 ) ≤ V ( γ ; I ) . Then, because the limits y 0 y_0 y 0 and y 1 y_1 y 1 are unique and in particular, do not depend on the representative for γ \gamma γ , taking the infimum over all representatives of γ \gamma γ gives
δ ( y 0 , y 1 ) ≤ inf γ ^ = γ a.e. V ( γ ^ ; I ) = ess V ( γ ; I ) = ∣ D γ ∣ ( I ) . \delta(y_0,y_1) \le\inf_{\widehat{\gamma}=\gamma\ \text{a.e.}} \mathbf{V}(\widehat{\gamma};I) = \operatorname{ess}\mathbf{V}(\gamma;I) = |D\gamma|(I). δ ( y 0 , y 1 ) ≤ γ = γ a.e. inf V ( γ ; I ) = ess V ( γ ; I ) = ∣ D γ ∣ ( I ) .
NOTATION. To stay consistent between the notation we are using for the boundary trace of a BV \operatorname{BV} BV -functions whose domain is not simply an interval, we will denote the points y 0 y_0 y 0 and y 1 y_1 y 1 in Y Y Y which satisfy the limit equations (14), by γ ∣ 0 \gamma|_0 γ ∣ 0 and γ ∣ 1 \gamma|_1 γ ∣ 1 , respectively.
Lemma 11. Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^{n} R n , let I = ( 0 , 1 ) I=(0,1) I = ( 0 , 1 ) , and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete separable metric space. If w ∈ BV ( Ω × I ; Y ) w\in\operatorname{BV}(\Omega\times I;Y) w ∈ BV ( Ω × I ; Y ) then for L n \mathcal{L}^{n} L n -a.e. x ∈ Ω x\in\Omega x ∈ Ω , the vertical restriction w x ∈ BV ( I ; Y ) w_x\in\operatorname{BV}(I;Y) w x ∈ BV ( I ; Y ) .
Proof. By definition of w ∈ BV ( Ω × I ; Y ) w\in\operatorname{BV}(\Omega\times I;Y) w ∈ BV ( Ω × I ; Y ) we can choose a finite Radon measure μ \mu μ on Ω × I \Omega\times I Ω × I such that
∣ D ( φ ∘ w ) ∣ ≤ μ for any φ ∈ Lip 1 ( Y ; R ) . |D(\varphi\circ w)|\leq\mu\qquad\text{for any }\varphi\in\operatorname{Lip}_{1}(Y;\mathbb{R}). ∣ D ( φ ∘ w ) ∣ ≤ μ for any φ ∈ Lip 1 ( Y ; R ) .
In the following we show that there is a single Radon measure with the same property on w x w_x w x for L n \mathcal{L}^{n} L n -a.e. x ∈ Ω x\in\Omega x ∈ Ω .
First we choose a countable dense subset { y i } \{y_i\} { y i } of Y Y Y and define
f i ( x , t ) : = δ ( w ( x , t ) , y i ) for all ( x , t ) ∈ Ω × I . f_i(x,t):=\delta(w(x,t),y_i)\qquad\text{for all }(x,t)\in\Omega\times I. f i ( x , t ) := δ ( w ( x , t ) , y i ) for all ( x , t ) ∈ Ω × I .
Because f i ∈ BV ( Ω × I ; R ) f_i\in\operatorname{BV}(\Omega\times I;\mathbb{R}) f i ∈ BV ( Ω × I ; R ) , the theorem for 1-dimensional restrictions of scalar-valued BV functions implies that for L n \mathcal{L}^{n} L n -a.e. x ∈ Ω x\in\Omega x ∈ Ω the one dimensional restriction ( f i ) x (f_i)_x ( f i ) x belongs to BV ( I ; R ) \operatorname{BV}(I;\mathbb{R}) BV ( I ; R ) . Since { f i } \{f_i\} { f i } are countable, there exists an L n \mathcal{L}^{n} L n -negligible set N N N such that for any i ∈ N i\in\mathbb{N} i ∈ N , the one-dimensional restriction ( f i ) x (f_i)_x ( f i ) x belongs to BV ( I ) \operatorname{BV}(I) BV ( I ) for all x ∈ Ω ∖ N x\in\Omega\setminus N x ∈ Ω ∖ N .
Now for such an x ∈ Ω ∖ N x\in\Omega\setminus N x ∈ Ω ∖ N , consider ⋁ i ∣ D ( f i ) x ∣ \bigvee_i|D(f_i)_x| ⋁ i ∣ D ( f i ) x ∣ , defined as the least measure dominating all the measures in { ∣ D ( f i ) x ∣ : i ∈ N } \{|D(f_i)_x|:i\in\mathbb{N}\} { ∣ D ( f i ) x ∣ : i ∈ N } . By [15, (1.7), (1.8)],
∫ Ω ⋁ i ∣ D ( f i ) x ∣ d L n ( x ) = ⋁ i ∫ Ω ∣ D ( f i ) x ∣ d L n ( x ) = ⋁ i ∣ D n + 1 f i ∣ ≤ ⋁ i ∣ D f i ∣ ≤ μ , \int_{\Omega}\bigvee_i|D(f_i)_x|\,d\mathcal{L}^{n}(x)=\bigvee_i\int_{\Omega}|D(f_i)_x|\,d\mathcal{L}^{n}(x)=\bigvee_i|D_{n+1}f_i|\leq\bigvee_i|Df_i|\leq\mu, ∫ Ω i ⋁ ∣ D ( f i ) x ∣ d L n ( x ) = i ⋁ ∫ Ω ∣ D ( f i ) x ∣ d L n ( x ) = i ⋁ ∣ D n + 1 f i ∣ ≤ i ⋁ ∣ D f i ∣ ≤ μ ,
and in particular,
∫ Ω ( ⋁ i ∣ D ( f i ) x ∣ ) ( I ) d L n ( x ) ≤ μ ( Ω × I ) < + ∞ . \int_{\Omega}\left(\bigvee_i|D(f_i)_x|\right)(I)\,d\mathcal{L}^{n}(x)\leq\mu(\Omega\times I)<+\infty. ∫ Ω ( i ⋁ ∣ D ( f i ) x ∣ ) ( I ) d L n ( x ) ≤ μ ( Ω × I ) < + ∞.
Thus there exists an L n \mathcal{L}^{n} L n -negligible set N ′ N' N ′ such that ⋁ i ∣ D ( f i ) x ∣ \bigvee_i|D(f_i)_x| ⋁ i ∣ D ( f i ) x ∣ is a finite Radon measure on I I I for every x ∈ Ω ∖ N ′ x\in\Omega\setminus N' x ∈ Ω ∖ N ′ , which in addition, bounds ∣ D ( f i ) x ∣ |D(f_i)_x| ∣ D ( f i ) x ∣ from above for any i ∈ N i\in\mathbb{N} i ∈ N and x ∈ Ω ∖ ( N ∪ N ′ ) x\in\Omega\setminus(N\cup N') x ∈ Ω ∖ ( N ∪ N ′ ) . Fix x ∈ Ω ∖ ( N ∪ N ′ ) x\in\Omega\setminus(N\cup N') x ∈ Ω ∖ ( N ∪ N ′ ) . For the remainder of the proof, we will show ∣ D ( φ ∘ w x ) ∣ ≤ ⋁ i ∣ D ( f i ) x ∣ |D(\varphi\circ w_x)|\leq\bigvee_i|D(f_i)_x| ∣ D ( φ ∘ w x ) ∣ ≤ ⋁ i ∣ D ( f i ) x ∣ for any φ ∈ Lip 1 ( Y ; R ) \varphi\in\operatorname{Lip}_{1}(Y;\mathbb{R}) φ ∈ Lip 1 ( Y ; R ) .
Any ( f i ) x (f_i)_x ( f i ) x has a representative that is continuous outside the set of jump points of the scalar-valued function [13, Theorem 3.28 (b)], and moreover, the set of jump points is at most countable since ∣ D ( f i ) x ∣ ( I ) < + ∞ |D(f_i)_x|(I)<+\infty ∣ D ( f i ) x ∣ ( I ) < + ∞ . Therefore we may choose a subset E x E_x E x of I I I , with L ( I ∖ E x ) = 0 \mathcal{L}(I\setminus E_x)=0 L ( I ∖ E x ) = 0 , on which any ( f i ) x (f_i)_x ( f i ) x agrees with a good representative that is continuous on E x E_x E x . Let s < t s<t s < t in E x E_x E x . Since
∣ ( f i ) x ( t ) − ( f i ) x ( s ) ∣ ≤ ∣ D ( f i ) x ∣ ( s , t ) ≤ ( ⋁ i ∣ D ( f i ) x ∣ ) ( s , t ) , |(f_i)_x(t)-(f_i)_x(s)|\leq|D(f_i)_x|(s,t)\leq\left(\bigvee_i|D(f_i)_x|\right)(s,t), ∣ ( f i ) x ( t ) − ( f i ) x ( s ) ∣ ≤ ∣ D ( f i ) x ∣ ( s , t ) ≤ ( i ⋁ ∣ D ( f i ) x ∣ ) ( s , t ) ,
we get
δ ( w x ( t ) , w x ( s ) ) = sup i ∣ ( f i ) x ( t ) − ( f i ) x ( s ) ∣ ≤ ( ⋁ i ∣ D ( f i ) x ∣ ) ( s , t ) . (18) \delta(w_x(t),w_x(s))=\sup_i|(f_i)_x(t)-(f_i)_x(s)|\leq\left(\bigvee_i|D(f_i)_x|\right)(s,t). \tag*{(18)} δ ( w x ( t ) , w x ( s )) = i sup ∣ ( f i ) x ( t ) − ( f i ) x ( s ) ∣ ≤ ( i ⋁ ∣ D ( f i ) x ∣ ) ( s , t ) . (18)
Let φ ∈ Lip 1 ( Y ) \varphi\in\operatorname{Lip}_{1}(Y) φ ∈ Lip 1 ( Y ) . To show w x ∈ BV ( I ; Y ) w_x\in\operatorname{BV}(I;Y) w x ∈ BV ( I ; Y ) , we first notice that φ ∘ w x ∈ L 1 ( I ) \varphi\circ w_x\in L^{1}(I) φ ∘ w x ∈ L 1 ( I ) follows from the bound ∣ φ ∘ w x ∣ ≤ ∣ φ ( y 1 ) ∣ + ( f 1 ) x |\varphi\circ w_x|\leq|\varphi(y_1)|+(f_1)_x ∣ φ ∘ w x ∣ ≤ ∣ φ ( y 1 ) ∣ + ( f 1 ) x . To conclude, it suffices to show that ∣ D ( φ ∘ w x ) ∣ ( J ) ≤ ⋁ i ∣ D ( f i ) x ∣ ( J ) |D(\varphi\circ w_x)|(J)\leq\bigvee_i|D(f_i)_x|(J) ∣ D ( φ ∘ w x ) ∣ ( J ) ≤ ⋁ i ∣ D ( f i ) x ∣ ( J ) for any open interval J ⊂ I J\subset I J ⊂ I . Towards that end, choose any finite sequence t 0 < ⋯ < t m t_0<\cdots<t_m t 0 < ⋯ < t m in E x ∩ J E_x\cap J E x ∩ J . Inequality (18) together with the fact that φ \varphi φ is 1-Lipschitz, gives us
∑ k ∣ φ ( w x ( t k ) ) − φ ( w x ( t k − 1 ) ) ∣ ≤ ∑ k ( ⋁ i ∣ D ( f i ) x ∣ ) ( t k − 1 , t k ) ≤ ( ⋁ i ∣ D ( f i ) x ∣ ) ( J ) . \sum_k|\varphi(w_x(t_k))-\varphi(w_x(t_{k-1}))|\leq\sum_k\left(\bigvee_i|D(f_i)_x|\right)(t_{k-1},t_k)\leq\left(\bigvee_i|D(f_i)_x|\right)(J). k ∑ ∣ φ ( w x ( t k )) − φ ( w x ( t k − 1 )) ∣ ≤ k ∑ ( i ⋁ ∣ D ( f i ) x ∣ ) ( t k − 1 , t k ) ≤ ( i ⋁ ∣ D ( f i ) x ∣ ) ( J ) .
Taking the supremum of the left-hand side over all partitions t 0 < ⋯ < t m t_0<\cdots<t_m t 0 < ⋯ < t m in E x ∩ J E_x\cap J E x ∩ J gives us ∣ D ( φ ∘ w x ) ∣ ( J ) ≤ ⋁ i ∣ D ( f i ) x ∣ ( J ) |D(\varphi\circ w_x)|(J)\leq\bigvee_i|D(f_i)_x|(J) ∣ D ( φ ∘ w x ) ∣ ( J ) ≤ ⋁ i ∣ D ( f i ) x ∣ ( J ) , therefore concluding the proof. ∕-?
Lemma 12. Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^{n} R n with Lipschitz boundary, and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete separable metric space. If the boundary trace w ∣ ∂ ( Ω × I ) ( x , t ) w|_{\partial(\Omega\times I)}(x,t) w ∣ ∂ ( Ω × I ) ( x , t ) of w ∈ BV ( Ω × I ; Y ) w\in\operatorname{BV}(\Omega\times I;Y) w ∈ BV ( Ω × I ; Y ) exists for a.e. ( x , t ) ∈ Ω × { 0 , 1 } (x,t)\in\Omega\times\{0,1\} ( x , t ) ∈ Ω × { 0 , 1 } , then
w x ∣ ∂ ( 0 , 1 ) ( t ) = w ∣ ∂ C ( x , t ) for a.e. ( x , t ) ∈ Ω × { 0 , 1 } . (19) w_{x}|_{\partial(0,1)}(t)=w|_{\partial\mathcal{C}}(x,t)\qquad\text{for a.e. }(x,t)\in\Omega\times\{0,1\}. \tag*{(19)} w x ∣ ∂ ( 0 , 1 ) ( t ) = w ∣ ∂ C ( x , t ) for a.e. ( x , t ) ∈ Ω × { 0 , 1 } . (19)
Proof. In the following, we prove (19) for t = 0 t=0 t = 0 . The case of t = 1 t=1 t = 1 follows from a similar argument. Suppose p ( x ) : = w ∣ ∂ ( Ω × I ) ( x , 0 ) p(x):=w|_{\partial(\Omega\times I)}(x,0) p ( x ) := w ∣ ∂ ( Ω × I ) ( x , 0 ) exist for a.e. x ∈ Ω x\in\Omega x ∈ Ω . We start our proof the same as in our proof of the existence of boundary traces for metric space valued BV functions. In particular, we choose a countable dense subset { y i } i ∈ N \{y_i\}_{i\in\mathbb{N}} { y i } i ∈ N of Y Y Y and for each i i i , define
v i ( x ) : = δ ( w ( x ) , y i ) for all x ∈ C . v_i(x):=\delta(w(x),y_i)\qquad\text{for all }x\in\mathcal{C}. v i ( x ) := δ ( w ( x ) , y i ) for all x ∈ C .
(Step 1 ) In the first step, we prove
( v i ) x ∣ ∂ I ( 0 ) = δ ( p ( x ) , y i ) for a.e. x ∈ Ω . (v_i)_x|_{\partial I}(0)=\delta(p(x),y_i)\qquad\text{for a.e. }x\in\Omega. ( v i ) x ∣ ∂ I ( 0 ) = δ ( p ( x ) , y i ) for a.e. x ∈ Ω.
Suppose the boundary trace of w w w exists at the point ( x , 0 ) (x,0) ( x , 0 ) , and is equal to p ( x ) p(x) p ( x ) . The reverse triangle inequality implies ∣ δ ( w , y i ) − δ ( p ( x ) , y i ) ∣ ≤ δ ( w , p ( x ) ) |\delta(w,y_i)-\delta(p(x),y_i)|\leq\delta(w,p(x)) ∣ δ ( w , y i ) − δ ( p ( x ) , y i ) ∣ ≤ δ ( w , p ( x )) , and hence v i ∣ ∂ ( Ω × I ) ( x , 0 ) = δ ( p ( x ) , y i ) v_i|_{\partial(\Omega\times I)}(x,0)=\delta(p(x),y_i) v i ∣ ∂ ( Ω × I ) ( x , 0 ) = δ ( p ( x ) , y i ) .
To show that the endpoint (boundary trace) of the vertical restriction of v i v_i v i is also δ ( p ( x ) , y i ) \delta(p(x),y_i) δ ( p ( x ) , y i ) we extend v i v_i v i to all of R n + 1 \mathbb{R}^{n+1} R n + 1 by defining
v ‾ i ( x , t ) : = { v i ( x , t ) if ( x , t ) ∈ Ω × I , 0 otherwise . \overline{v}_i(x,t):=
\begin{cases}
v_i(x,t) & \text{if }(x,t)\in\Omega\times I,\\
0 & \text{otherwise}.
\end{cases} v i ( x , t ) := { v i ( x , t ) 0 if ( x , t ) ∈ Ω × I , otherwise .
Notice that because the one-sided approximate limit ( v ‾ i ) ν + ( x , 0 ) (\overline{v}_i)_{\boldsymbol{\nu}}^{+}(x,0) ( v i ) ν + ( x , 0 ) in the positive vertical direction ν \boldsymbol{\nu} ν agrees with the boundary trace v i ∣ ∂ ( Ω × I ) ( x , 0 ) v_i|_{\partial(\Omega\times I)}(x,0) v i ∣ ∂ ( Ω × I ) ( x , 0 ) ,
( v ‾ i ) ν + ( x , 0 ) = δ ( p ( x ) , y i ) and ( v ‾ i ) ν − ( x , 0 ) = 0. (\overline{v}_i)_{\boldsymbol{\nu}}^{+}(x,0)=\delta(p(x),y_i)\qquad\text{and}\qquad(\overline{v}_i)_{\boldsymbol{\nu}}^{-}(x,0)=0. ( v i ) ν + ( x , 0 ) = δ ( p ( x ) , y i ) and ( v i ) ν − ( x , 0 ) = 0.
By Remark 3.109 (also see Theorem 3.108(a)) of AFP’s monograph [13], for L n \mathcal{L}^{n} L n -a.e. x ∈ Ω x\in\Omega x ∈ Ω ,
{ x } × J ( v ‾ i ) x = J v ‾ i ∩ { ( x , t ) : t ∈ R } . (20) \{x\}\times J_{(\overline{v}_i)_x}=J_{\overline{v}_i}\cap\{(x,t):t\in\mathbb{R}\}. \tag*{(20)} { x } × J ( v i ) x = J v i ∩ {( x , t ) : t ∈ R } . (20)
Let x x x be a point in Ω \Omega Ω satisfying (20) along with the one-sided identities of Remark 3.109. There are two cases to consider: either δ ( p ( x 0 ) , y i ) = 0 \delta(p(x_0),y_i)=0 δ ( p ( x 0 ) , y i ) = 0 , or δ ( p ( x 0 ) , y i ) > 0 \delta(p(x_0),y_i)>0 δ ( p ( x 0 ) , y i ) > 0 .
Assuming the former, then v ‾ i \overline{v}_i v i is approximately continuous at ( x , 0 ) (x,0) ( x , 0 ) , and therefore, (20) implies ( v ‾ i ) x (\overline{v}_i)_x ( v i ) x is also approximately continuous at t = 0 t=0 t = 0 . Because the one-sided traces of v ‾ i \overline{v}_i v i and ( v ‾ i ) x (\overline{v}_i)_x ( v i ) x are 0 in the negative ν \boldsymbol{\nu} ν direction, this would require their one-sided traces in the positive ν \boldsymbol{\nu} ν direction to also be 0, and thus, the endpoint trace of ( v ‾ i ) x (\overline{v}_i)_x ( v i ) x at t = 0 t=0 t = 0 equals δ ( p ( x ) , y i ) \delta(p(x),y_i) δ ( p ( x ) , y i ) .
In the case that δ ( p ( x ) , y i ) > 0 \delta(p(x),y_i)>0 δ ( p ( x ) , y i ) > 0 , then ( x , 0 ) (x,0) ( x , 0 ) is a jump point of v ‾ i \overline{v}_i v i , and therefore, t = 0 t=0 t = 0 is a jump point of its vertical restriction ( v ‾ i ) x (\overline{v}_i)_x ( v i ) x . By definition, the one-sided trace of ( v ‾ i ) x (\overline{v}_i)_x ( v i ) x exists at 0 and is equal to the end-point trace of ( v i ) x (v_i)_x ( v i ) x at 0, so by [13, Remark 3.109],
(v_i)_x|_{\partial I}(0)=\lim_{r\to0+}\fint_{(0,r)}(\overline{v}_i)_x\,d\mathcal{L}=(\overline{v}_i)_{\boldsymbol{\nu}}^{+}(x,0).
(Step 2 ) Fix an x ∈ Ω x\in\Omega x ∈ Ω such that Step 1 holds for every i i i , w x ∈ BV ( I ; Y ) w_x\in\operatorname{BV}(I;Y) w x ∈ BV ( I ; Y ) , and its endpoint trace exists at 0. Set y ∗ : = w x ∣ ∂ I ( 0 ) y^{*}:=w_x|_{\partial I}(0) y ∗ := w x ∣ ∂ I ( 0 ) . Lemma 11 and countability of y i y_i y i implies such conditions hold L n \mathcal{L}^n L n -a.e. in Ω \Omega Ω . The reverse triangle inequality implies
\lim_{r\to0+}\fint_{(0,r)} \left|\delta(w_x(t),y_i)-\delta(y^*,y_i)\right|\,dt \le\lim_{r\to0+}\fint_{(0,r)}\delta(w_x(t),y^*)\,dt=0 \quad\text{for any }i\in\mathbb{N}.
Hence, ( v i ) x ∣ ∂ I ( 0 ) = δ ( y ∗ , y i ) (v_i)_x|_{\partial I}(0)=\delta(y^*,y_i) ( v i ) x ∣ ∂ I ( 0 ) = δ ( y ∗ , y i ) . However, we already showed that the endpoint trace of ( v i ) x (v_i)_x ( v i ) x is equal to δ ( p ( x ) , y i ) \delta(p(x),y_i) δ ( p ( x ) , y i ) .
This implies that δ ( y ∗ , y i ) = δ ( p ( x ) , y i ) \delta(y^*,y_i)=\delta(p(x),y_i) δ ( y ∗ , y i ) = δ ( p ( x ) , y i ) for all i ∈ N i\in\mathbb{N} i ∈ N . Because { y i } \{y_i\} { y i } is dense Y Y Y , y ∗ = p ( x ) y^*=p(x) y ∗ = p ( x ) . □ \square □
Minimizing the Horizontal Total Variation
In this section, we prove the following theorem.
Theorem 13. Let Y Y Y be a complete, separable metric space and let p , q ∈ BV ( Ω ; Y ) p,q\in\operatorname{BV}(\Omega;Y) p , q ∈ BV ( Ω ; Y ) where Ω ⊂ R n \Omega\subset\mathbb{R}^n Ω ⊂ R n is bounded, connected, and open. Then
min w ∈ BV ( Ω × I ; Y ) w ∣ Ω × 0 = p a.e. w ∣ Ω × 1 = q a.e. ∫ Ω ∣ D w x ∣ ( 0 , 1 ) d L n ( x ) = ∫ Ω δ ( p , q ) d L n (21) \min_{\substack{w\in\operatorname{BV}(\Omega\times I;Y)\\ w|_{\Omega\times0}=p\ \text{a.e.}\\ w|_{\Omega\times1}=q\ \text{a.e.}}}\int_\Omega|D w_x|(0,1)\,d\mathcal{L}^n(x)=\int_\Omega\delta(p,q)\,d\mathcal{L}^n \tag*{(21)} w ∈ BV ( Ω × I ; Y ) w ∣ Ω × 0 = p a.e. w ∣ Ω × 1 = q a.e. min ∫ Ω ∣ D w x ∣ ( 0 , 1 ) d L n ( x ) = ∫ Ω δ ( p , q ) d L n (21) and the minimum is achieved.
The quantity ∫ Ω ∣ D w x ∣ ( I ) \int_\Omega|D w_x|(I) ∫ Ω ∣ D w x ∣ ( I ) is also denoted by ∣ ⟨ D w x , e n + 1 ⟩ ∣ |\langle D w_x,e_{n+1}\rangle| ∣ ⟨ D w x , e n + 1 ⟩ ∣ , in particular, because it agrees with the total variation of the weak derivative of w w w in the direction e n + 1 e_{n+1} e n + 1 whenever w w w is a vector-valued BV function. In the case of a piecewise-constant filling between p p p and q q q (defined in the next section), ∣ ⟨ D w x , e n + 1 ⟩ ∣ ( Ω × I ) |\langle D w_x,e_{n+1}\rangle|(\Omega\times I) ∣ ⟨ D w x , e n + 1 ⟩ ∣ ( Ω × I ) will agree with the surface energy of the L 1 L^1 L 1 -approximate discontinuity set of w w w . Our volume exchange metric will be defined, in part, by minimizing this surface energy and Theorem 6 will be a corollary of the previous result.
We separately prove that the left hand side of (21) is greater than or equal to the right hand side in Proposition 14 and the reverse inequality in Lemma 15. This suffices to show the preceding theorem.
Proposition 14. Let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^n R n , and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete separable metric space. If w ∈ BV ( Ω × I ; Y ) w\in\operatorname{BV}(\Omega\times I;Y) w ∈ BV ( Ω × I ; Y ) has boundary traces p p p and q q q at Ω × 0 \Omega\times0 Ω × 0 and Ω × 1 \Omega\times1 Ω × 1 , respectively, then
∫ Ω δ ( p , q ) d L n ≤ ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) . \int_\Omega\delta(p,q)\,d\mathcal{L}^n\leq\int_\Omega|D w_x|(I)\,d\mathcal{L}^n(x). ∫ Ω δ ( p , q ) d L n ≤ ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) .
Proof. By Lemma 11 w x ∈ BV ( Ω ; Y ) w_x\in\operatorname{BV}(\Omega;Y) w x ∈ BV ( Ω ; Y ) for L n \mathcal{L}^n L n -a.e. x ∈ Ω x\in\Omega x ∈ Ω . Thus, by Lemma 12 and the upper bound (15)
∫ Ω δ ( p , q ) d L n = ∫ Ω δ ( w x ∣ 0 , w x ∣ 1 ) d L n ( x ) ≤ ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) . \int_\Omega\delta(p,q)\,d\mathcal{L}^n=\int_\Omega\delta(w_x|_0,w_x|_1)\,d\mathcal{L}^n(x)\leq\int_\Omega|D w_x|(I)\,d\mathcal{L}^n(x). ∫ Ω δ ( p , q ) d L n = ∫ Ω δ ( w x ∣ 0 , w x ∣ 1 ) d L n ( x ) ≤ ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) .
□ \square □
We now show that directional weak derivative of the step-function w w w (defined below in Equation (22) ) that jumps from p p p to q q q at some point between 0 and 1 is exactly the L 1 L^1 L 1 -norm of δ ( p , q ) \delta(p,q) δ ( p , q ) .
Lemma 15. Let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete separable metric space, let Ω \Omega Ω be a bounded, connected, open subset of R n \mathbb{R}^{n} R n , and let p , q ∈ BV ( Ω ; Y ) p,q \in\operatorname{BV}(\Omega;Y) p , q ∈ BV ( Ω ; Y ) . The step-function w ∗ : Ω × I → Y w^{*}:\Omega\times I \to Y w ∗ : Ω × I → Y defined by the equation
w ∗ ( x , t ) : = { p ( x ) if ( x , t ) ∈ Ω × ( 0 , 1 / 2 ] q ( x ) if ( x , t ) ∈ Ω × ( 1 / 2 , 1 ) , (22) w^{*}(x,t):=
\begin{cases}
p(x) & \text{if } (x,t)\in\Omega\times(0,1/2] \\
q(x) & \text{if } (x,t)\in\Omega\times(1/2,1),
\end{cases} \tag*{(22)} w ∗ ( x , t ) := { p ( x ) q ( x ) if ( x , t ) ∈ Ω × ( 0 , 1/2 ] if ( x , t ) ∈ Ω × ( 1/2 , 1 ) , (22) which jumps from p p p to q q q at t = 1 / 2 t=1/2 t = 1/2 , has the following properties.
(a) w ∗ ∈ BV ( Ω × I ; Y ) w^{*}\in\operatorname{BV}(\Omega\times I;Y) w ∗ ∈ BV ( Ω × I ; Y ) ;
(b) the boundary trace of w ∗ w^{*} w ∗ exists and is given by
w ∗ ∣ Ω × 0 ( x , 0 ) = p ( x ) and w ∗ ∣ Ω × 1 ( x , 1 ) = q ( x ) for L n -a.e. x ∈ Ω ; w^{*}|_{\Omega\times0}(x,0)=p(x) \qquad\text{and}\qquad w^{*}|_{\Omega\times1}(x,1)=q(x) \qquad\text{for }\mathcal{L}^{n}\text{-a.e. }x\in\Omega; w ∗ ∣ Ω × 0 ( x , 0 ) = p ( x ) and w ∗ ∣ Ω × 1 ( x , 1 ) = q ( x ) for L n -a.e. x ∈ Ω ; (c)
∫ Ω ∣ D x w x ∣ ( I ) d L n ( x ) = ∥ δ ( p , q ) ∥ L 1 ( Ω ) . \int_{\Omega}|D_{x}w_{x}|(I)\,d\mathcal{L}^{n}(x)=\|\delta(p,q)\|_{L^{1}(\Omega)}. ∫ Ω ∣ D x w x ∣ ( I ) d L n ( x ) = ∥ δ ( p , q ) ∥ L 1 ( Ω ) .
Proof. (a) We will show w ∗ w^{*} w ∗ is in BV ( Ω × I ; Y ) \operatorname{BV}(\Omega\times I;Y) BV ( Ω × I ; Y ) by definition. First notice that the triangle inequality implies w ∗ ∈ L 1 ( Ω × I ; Y ) w^{*}\in L^{1}(\Omega\times I;Y) w ∗ ∈ L 1 ( Ω × I ; Y ) . Let φ : Y → R \varphi:Y\to\mathbb{R} φ : Y → R be an arbitrary 1-Lipschitz function, and let us denote the post-compositions of w ∗ w^{*} w ∗ , p p p and q q q with φ \varphi φ by v v v , v 0 v_{0} v 0 and v 1 v_{1} v 1 , respectively.
Let us now compute the weak derivatives of v v v . Let ϕ ∈ C c ∞ ( Ω × I ; R ) \phi\in C^{\infty}_{c}(\Omega\times I;\mathbb{R}) ϕ ∈ C c ∞ ( Ω × I ; R ) and first fix j ∈ { 1 , … , n } j\in\{1,\ldots,n\} j ∈ { 1 , … , n } . Because the map x ↦ ϕ ( x , t ) x\mapsto\phi(x,t) x ↦ ϕ ( x , t ) is in C c ∞ ( Ω ; R ) C^{\infty}_{c}(\Omega;\mathbb{R}) C c ∞ ( Ω ; R ) for any t ∈ I t\in I t ∈ I , we get
∫ Ω v i ( x ) ∂ j ϕ ( x , t ) d L n ( x ) = − ∫ Ω ϕ ( x , t ) d D j v i ( x ) for i = 0 , 1 and t ∈ I . (23) \int_{\Omega}v_{i}(x)\partial_{j}\phi(x,t)\,d\mathcal{L}^{n}(x)
=-\int_{\Omega}\phi(x,t)\,dD_{j}v_{i}(x)
\qquad\text{for }i=0,1\text{ and }t\in I. \tag*{(23)} ∫ Ω v i ( x ) ∂ j ϕ ( x , t ) d L n ( x ) = − ∫ Ω ϕ ( x , t ) d D j v i ( x ) for i = 0 , 1 and t ∈ I . (23)
Together with Fubini’s theorem and the definition of w w w , this implies
∫ Ω × ( 0 , 1 ) v ∂ j ϕ d L n + 1 = − ∫ ( 0 , 1 / 2 ) ( ∫ Ω ϕ d D j v 0 ) d L − ∫ ( 1 / 2 , 1 ) ( ∫ Ω ϕ d D j v 1 ) d L , \int_{\Omega\times(0,1)}v\,\partial_{j}\phi\,d\mathcal{L}^{n+1}
=-\int_{(0,1/2)}\left(\int_{\Omega}\phi\,dD_{j}v_{0}\right)d\mathcal{L}
-\int_{(1/2,1)}\left(\int_{\Omega}\phi\,dD_{j}v_{1}\right)d\mathcal{L}, ∫ Ω × ( 0 , 1 ) v ∂ j ϕ d L n + 1 = − ∫ ( 0 , 1/2 ) ( ∫ Ω ϕ d D j v 0 ) d L − ∫ ( 1/2 , 1 ) ( ∫ Ω ϕ d D j v 1 ) d L ,
and thus
D j v = D j v 0 L ⌞ ( 0 , 1 / 2 ) + D j v 1 L ⌞ ( 1 / 2 , 1 ) . (24) D_{j}v=D_{j}v_{0}\,\mathcal{L}\llcorner(0,1/2)+D_{j}v_{1}\,\mathcal{L}\llcorner(1/2,1). \tag*{(24)} D j v = D j v 0 L └ ( 0 , 1/2 ) + D j v 1 L └ ( 1/2 , 1 ) . (24)
For j = n + 1 j=n+1 j = n + 1 , because the map t ↦ ϕ ( x , t ) t\mapsto\phi(x,t) t ↦ ϕ ( x , t ) is smooth and compactly supported on I I I (for any x ∈ Ω x\in\Omega x ∈ Ω ), the definition of v v v implies
∫ ( 0 , 1 ) v ( x , t ) ∂ n + 1 ϕ ( x , t ) d t = ( v 0 ( x ) − v 1 ( x ) ) ϕ ( x , 1 / 2 ) . \int_{(0,1)}v(x,t)\,\partial_{n+1}\phi(x,t)\,dt=(v_{0}(x)-v_{1}(x))\phi(x,1/2). ∫ ( 0 , 1 ) v ( x , t ) ∂ n + 1 ϕ ( x , t ) d t = ( v 0 ( x ) − v 1 ( x )) ϕ ( x , 1/2 ) .
and thus
D n + 1 v = ( v 1 − v 0 ) H n ⌞ Ω × { 1 / 2 } . (25) D_{n+1}v=(v_{1}-v_{0})\mathcal{H}^{n}\llcorner\Omega\times\{1/2\}. \tag*{(25)} D n + 1 v = ( v 1 − v 0 ) H n └ Ω × { 1/2 } . (25)
Now by definition, there exists finite measures σ 0 \sigma_{0} σ 0 and σ 1 \sigma_{1} σ 1 on Ω \Omega Ω such that ∣ D ( φ ∘ p ) ∣ ≤ σ 0 |D(\varphi\circ p)|\leq\sigma_{0} ∣ D ( φ ∘ p ) ∣ ≤ σ 0 and ∣ D ( φ ∘ q ) ∣ ≤ σ 0 |D(\varphi\circ q)|\leq\sigma_{0} ∣ D ( φ ∘ q ) ∣ ≤ σ 0 for any 1-Lipschitz function φ : Y → R \varphi:Y\to\mathbb{R} φ : Y → R . Thus,
∣ D v ∣ ≤ σ 0 ⊗ L 1 ⌞ ( 0 , 1 / 2 ) + σ 1 ⊗ L 1 ⌞ ( 1 / 2 , 1 ) + δ ( p , q ) H n ⌞ ( Ω × { 1 / 2 } ) . |Dv|\leq\sigma_{0}\otimes\mathcal{L}^{1}\llcorner(0,1/2)+\sigma_{1}\otimes\mathcal{L}^{1}\llcorner(1/2,1)+\delta(p,q)\mathcal{H}^{n}\llcorner(\Omega\times\{1/2\}). ∣ D v ∣ ≤ σ 0 ⊗ L 1 └ ( 0 , 1/2 ) + σ 1 ⊗ L 1 └ ( 1/2 , 1 ) + δ ( p , q ) H n └ ( Ω × { 1/2 }) .
Since the measure bounding ∣ D v ∣ |Dv| ∣ D v ∣ has total a total mass of 1 2 σ 0 ( Ω ) + 1 2 σ 1 ( Ω ) + ∫ Ω δ ( p , q ) < + ∞ \frac{1}{2}\sigma_{0}(\Omega)+\frac{1}{2}\sigma_{1}(\Omega)+\int_{\Omega}\delta(p,q)<+\infty 2 1 σ 0 ( Ω ) + 2 1 σ 1 ( Ω ) + ∫ Ω δ ( p , q ) < + ∞ , and since φ \varphi φ was an arbitrary, we have shown w ∗ w^{*} w ∗ is in BV ( Ω ; Y ) \operatorname{BV}(\Omega;Y) BV ( Ω ; Y ) .
(b) We now show that the boundary trace of w ∗ w^{*} w ∗ exists at the bottom Ω × 0 \Omega\times0 Ω × 0 of the cylinder Ω × I \Omega\times I Ω × I ; a similar argument can be made for the top Ω × 1 \Omega\times1 Ω × 1 of the cylinder. By Proposition 9 the L 1 L^{1} L 1 -approximate limit of p p p exists and is equal to p ( x 0 ) p(x_{0}) p ( x 0 ) for L n \mathcal{L}^{n} L n -a.e. x 0 ∈ Ω x_{0}\in\Omega x 0 ∈ Ω . Therefore, for any such x 0 ∈ Ω x_{0}\in\Omega x 0 ∈ Ω , since B ( ( x 0 , t ) , r ) ⊂ B ( x 0 , r ) × [ 0 , r ) B((x_{0},t),r)\subset B(x_{0},r)\times[0,r) B (( x 0 , t ) , r ) ⊂ B ( x 0 , r ) × [ 0 , r ) and
∫ B ( x 0 , r ) × [ 0 , r ) δ ( w , p ( x 0 ) ) d L n + 1 = r ∫ B ( x 0 , r ) δ ( p , p ( x 0 ) ) d L n , \int_{B(x_{0},r)\times[0,r)}\delta(w,p(x_{0}))\,d\mathcal{L}^{n+1}
=r\int_{B(x_{0},r)}\delta(p,p(x_{0}))\,d\mathcal{L}^{n}, ∫ B ( x 0 , r ) × [ 0 , r ) δ ( w , p ( x 0 )) d L n + 1 = r ∫ B ( x 0 , r ) δ ( p , p ( x 0 )) d L n ,
@ we get that for small enough r > 0 r > 0 r > 0 ,
∫ Ω × ( 0 , 1 ) ∩ B ( ( x 0 , 0 ) , r ) δ ( w ∗ , p ( x 0 ) ) d L n + 1 ≤ r 1 2 ω n + 1 r n + 1 ∫ B ( x 0 , r ) δ ( p , p ( x 0 ) ) d L n = 2 ω n ω n + 1 ∫ B ( x 0 , r ) δ ( p , p ( x 0 ) ) d L n ⟶ 0 \int_{\Omega\times(0,1)\cap B((x_0,0),r)} \delta(w^*,p(x_0))\,d\mathcal{L}^{n+1}
\le\frac{r}{\frac{1}{2}\omega_{n+1}r^{n+1}}\int_{B(x_0,r)}\delta(p,p(x_0))\,d\mathcal{L}^n
= \frac{2\omega_n}{\omega_{n+1}}\int_{B(x_0,r)}\delta(p,p(x_0))\,d\mathcal{L}^n \longrightarrow0 ∫ Ω × ( 0 , 1 ) ∩ B (( x 0 , 0 ) , r ) δ ( w ∗ , p ( x 0 )) d L n + 1 ≤ 2 1 ω n + 1 r n + 1 r ∫ B ( x 0 , r ) δ ( p , p ( x 0 )) d L n = ω n + 1 2 ω n ∫ B ( x 0 , r ) δ ( p , p ( x 0 )) d L n ⟶ 0
as r → 0 + r \to0+ r → 0 + . Hence by the definition, the boundary trace of w ∗ w^* w ∗ exists for L n \mathcal{L}^n L n -a.e. x 0 ∈ Ω x_0 \in\Omega x 0 ∈ Ω and is equal to p ( x 0 ) p(x_0) p ( x 0 ) .
(c) We now prove the final part of the Lemma. For each x ∈ Ω x \in\Omega x ∈ Ω , the vertical slice w x ∗ w_x^* w x ∗ is a step function which jumps from p ( x ) p(x) p ( x ) to q ( x ) q(x) q ( x ) at t = 1 / 2 t = 1/2 t = 1/2 . Because w x ∗ w_x^* w x ∗ minimizes the variation over any representative of w x ∗ w_x^* w x ∗ , and because essV ( w x ∗ ; ( 0 , 1 ) ) = ∣ D w x ∗ ∣ ( I ) \operatorname{essV}(w_x^*;(0,1)) = |Dw_x^*|(I) essV ( w x ∗ ; ( 0 , 1 )) = ∣ D w x ∗ ∣ ( I ) , we get δ ( p , q ) = V ( w x ∗ ; ( 0 , 1 ) ) = ∣ D w x ∗ ∣ ( I ) \delta(p,q) = V(w_x^*;(0,1)) = |Dw_x^*|(I) δ ( p , q ) = V ( w x ∗ ; ( 0 , 1 )) = ∣ D w x ∗ ∣ ( I ) . Hence
∫ Ω δ ( p ( x ) , q ( x ) ) d L n = ∫ Ω ∣ D w x ∗ ∣ ( I ) d L n . \int_{\Omega}\delta(p(x),q(x))\,d\mathcal{L}^n=\int_{\Omega}|Dw_x^*|(I)\,d\mathcal{L}^n. ∫ Ω δ ( p ( x ) , q ( x )) d L n = ∫ Ω ∣ D w x ∗ ∣ ( I ) d L n .
Rectifiability of approximate discontinuity set and existence of boundary traces
Theorem 16. Suppose ( Y , δ ) (Y,\delta) ( Y , δ ) is a complete and separable metric space, and suppose w ∈ BV ( Ω ; Y ) w \in\operatorname{BV}(\Omega;Y) w ∈ BV ( Ω ; Y ) . Then S w S_w S w is countably H n − 1 \mathcal{H}^{n-1} H n − 1 -rectifiable, and there exist Borel maps
n : S w → S n − 1 , w + , w − : S w → Y n:S_w\to S^{n-1},\qquad w^+,w^-:S_w\to Y n : S w → S n − 1 , w + , w − : S w → Y
such that n n n orients S w S_w S w and, for H n − 1 \mathcal{H}^{n-1} H n − 1 -almost every x 0 ∈ S w x_0 \in S_w x 0 ∈ S w ,
\lim_{r\to0}\fint_{B^{\pm}_{n}(x_0,r)}\delta(w,w^{\pm}(x_0))\,d\mathcal{L}^n=0
\qquad\text{and}\qquad w^+(x_0)\ne w^-(x_0).
Proof. Let { y i } \{y_i\} { y i } be a countable dense subset of Y Y Y , and suppose y 1 y_1 y 1 is chosen such that δ ( w , y 1 ) ∈ L 1 ( Ω ) \delta(w,y_1)\in L^1(\Omega) δ ( w , y 1 ) ∈ L 1 ( Ω ) – which we may assume exists by the definition of the class BV ( Ω ; Y ) \operatorname{BV}(\Omega;Y) BV ( Ω ; Y ) . In addition, define
f i ( x ) : = δ ( w ( x ) , y i ) and v N ( x ) : = min i ≤ N f i ( x ) (26) f_i(x):=\delta(w(x),y_i)
\qquad\text{and}\qquad
v_N(x):=\min_{i\le N}f_i(x) \tag*{(26)} f i ( x ) := δ ( w ( x ) , y i ) and v N ( x ) := i ≤ N min f i ( x ) (26)
for each N ∈ N N\in\mathbb{N} N ∈ N .
( Step 1 ) (\text{Step 1}) ( Step 1 ) The distance function y ↦ min i ≤ N δ ( y , y i ) y\mapsto\min_{i\le N}\delta(y,y_i) y ↦ min i ≤ N δ ( y , y i ) is 1-Lipschitz. Hence, by the definition of the class BV ( Ω ; Y ) \operatorname{BV}(\Omega;Y) BV ( Ω ; Y ) , v N ∈ BV ( Ω ) v_N\in\operatorname{BV}(\Omega) v N ∈ BV ( Ω ) for any N N N , and there exists a finite Radon measure μ \mu μ on Ω \Omega Ω such that ∣ D v N ∣ ≤ μ |Dv_N|\le\mu ∣ D v N ∣ ≤ μ for all N N N .
Moreover, because 0 ≤ v N + 1 ≤ v N ≤ δ ( w , y 1 ) 0\le v_{N+1}\le v_N\le\delta(w,y_1) 0 ≤ v N + 1 ≤ v N ≤ δ ( w , y 1 ) and v N → 0 v_N\to0 v N → 0 as N → ∞ N\to\infty N → ∞ , the dominated convergence theorem gives us that
lim N → 0 ∥ v N ∥ L 1 ( Ω ; R ) = 0. \lim_{N\to0}\|v_N\|_{L^1(\Omega;\mathbb{R})}=0. N → 0 lim ∥ v N ∥ L 1 ( Ω ; R ) = 0.
Now, by the Radon-Nikodym theorem, there exists an L 1 L^1 L 1 -summable function g N : Ω → R n g_N:\Omega\to\mathbb{R}^n g N : Ω → R n such that D v N = g N μ Dv_N=g_N\mu D v N = g N μ . Notice that we also have ∣ g N ( x ) ∣ ≤ 1 |g_N(x)|\le1 ∣ g N ( x ) ∣ ≤ 1 for μ \mu μ -a.e. x ∈ Ω x\in\Omega x ∈ Ω . Together with the definition of the weak-derivative of v N v_N v N , this implies that for any φ ∈ C c 1 ( Ω ; R n ) \varphi\in C^1_c(\Omega;\mathbb{R}^n) φ ∈ C c 1 ( Ω ; R n ) we have
∫ Ω φ ⋅ g N d μ = − ∫ Ω v N div φ d L n ⟶ 0 as N → ∞ . (27) \int_{\Omega}\varphi\cdot g_N\,d\mu=-\int_{\Omega}v_N\operatorname{div}\varphi\,d\mathcal{L}^n\longrightarrow0\quad\text{as }N\to\infty. \tag*{(27)} ∫ Ω φ ⋅ g N d μ = − ∫ Ω v N div φ d L n ⟶ 0 as N → ∞. (27)
Now, because μ \mu μ is a finite Radon measure on Ω \Omega Ω , C c 1 ( Ω ; R n ) C^1_c(\Omega;\mathbb{R}^n) C c 1 ( Ω ; R n ) is dense in L 1 ( μ ; R n ) L^1(\mu;\mathbb{R}^n) L 1 ( μ ; R n ) and L ∞ ( μ ; R n ) ⊂ L 1 ( μ ; R n ) L^\infty(\mu;\mathbb{R}^n) \subset L^1(\mu;\mathbb{R}^n) L ∞ ( μ ; R n ) ⊂ L 1 ( μ ; R n ) , for any ε > 0 \varepsilon> 0 ε > 0 , and ψ ∈ L ∞ ( μ ; R n ) \psi\in L^\infty(\mu;\mathbb{R}^n) ψ ∈ L ∞ ( μ ; R n ) , we can pick ϕ ∈ C c 1 ( μ ; R n ) \phi\in C^1_c(\mu;\mathbb{R}^n) ϕ ∈ C c 1 ( μ ; R n ) such that
∥ ψ − ϕ ∥ L 1 ( μ ; R n ) < ε . \lVert\psi-\phi\rVert_{L^1(\mu;\mathbb{R}^n)}<\varepsilon. ∥ ψ − ϕ ∥ L 1 ( μ ; R n ) < ε .
Writing ∫ Ω ψ ⋅ g N d μ = ∫ Ω ϕ ⋅ g N d μ + ∫ Ω ( ψ − ϕ ) ⋅ g N d μ \int_{\Omega}\psi\cdot g_N\,d\mu=\int_{\Omega}\phi\cdot g_N\,d\mu+\int_{\Omega}(\psi-\phi)\cdot g_N\,d\mu ∫ Ω ψ ⋅ g N d μ = ∫ Ω ϕ ⋅ g N d μ + ∫ Ω ( ψ − ϕ ) ⋅ g N d μ , the uniform boundedness of g N g_N g N , and (27), this implies g N g_N g N converges weakly to 0 0 0 in L 1 ( Ω ) L^1(\Omega) L 1 ( Ω ) . Strong convergence of v N v_N v N to 0 0 0 in L 1 ( Ω ; R ) L^1(\Omega;\mathbb{R}) L 1 ( Ω ; R ) together with weak convergence of g N g_N g N to 0 0 0 in L 1 ( μ ; R n ) L^1(\mu;\mathbb{R}^n) L 1 ( μ ; R n ) implies the ordered pair ( v N , g N ) (v_N,g_N) ( v N , g N ) converges weakly to ( 0 , 0 ) (0,0) ( 0 , 0 ) in the Banach space L 1 ( Ω ) × L 1 ( μ ; R n ) L^1(\Omega)\times L^1(\mu;\mathbb{R}^n) L 1 ( Ω ) × L 1 ( μ ; R n ) .
By Mazur’s lemma, for m ∈ N m\in\mathbb{N} m ∈ N , there exist finite convex combinations
( u m , h m ) = ∑ i = m K m λ i m ( v i , g i ) where ∥ u m ∥ L 1 ( Ω ) + ∥ h m ∥ L 1 ( μ ; R n ) → 0. (u_m,h_m)=\sum_{i=m}^{K_m}\lambda_i^m(v_i,g_i)\qquad\text{where}\qquad\lVert u_m\rVert_{L^1(\Omega)}+\lVert h_m\rVert_{L^1(\mu;\mathbb{R}^n)}\to0. ( u m , h m ) = i = m ∑ K m λ i m ( v i , g i ) where ∥ u m ∥ L 1 ( Ω ) + ∥ h m ∥ L 1 ( μ ; R n ) → 0.
Since D u m = h m μ Du_m=h_m\mu D u m = h m μ , we get that
∥ u m ∥ B V ( Ω ) → 0. (28) \lVert u_m\rVert_{\mathrm{BV}(\Omega)}\to0. \tag*{(28)} ∥ u m ∥ BV ( Ω ) → 0. (28)
This provides us with a subsequence { u m k } \{u_{m_k}\} { u m k } such that ∑ k = 1 ∞ ∥ u m k ∥ B V ( Ω ) < + ∞ \sum_{k=1}^{\infty}\lVert u_{m_k}\rVert_{\mathrm{BV}(\Omega)}<+\infty ∑ k = 1 ∞ ∥ u m k ∥ BV ( Ω ) < + ∞ , which we note, implies
u : = ∑ k = 1 ∞ u m k ∈ B V ( Ω ) . u:=\sum_{k=1}^{\infty}u_{m_k}\in\mathrm{BV}(\Omega). u := k = 1 ∑ ∞ u m k ∈ BV ( Ω ) .
Let M ∈ N M\in\mathbb{N} M ∈ N and N M : = max { K m 1 , … , K m M } N_M:=\max\{K_{m_1},\ldots,K_{m_M}\} N M := max { K m 1 , … , K m M } . For any N ≥ N M N\geq N_M N ≥ N M we have
M v N ≤ ∑ k = 1 M v K m k ≤ ∑ k = 1 M ∑ i = m k K m k λ i m k v i = ∑ k = 1 M u m k ≤ u . (29) M v_N\leq\sum_{k=1}^{M}v_{K_{m_k}}\leq\sum_{k=1}^{M}\sum_{i=m_k}^{K_{m_k}}\lambda_i^{m_k}v_i=\sum_{k=1}^{M}u_{m_k}\leq u. \tag*{(29)} M v N ≤ k = 1 ∑ M v K m k ≤ k = 1 ∑ M i = m k ∑ K m k λ i m k v i = k = 1 ∑ M u m k ≤ u . (29)
(Step 2) Define
Γ : = S u ∪ ⋃ i = 1 ∞ S f i . \Gamma:=S_u\cup\bigcup_{i=1}^{\infty}S_{f_i}. Γ := S u ∪ i = 1 ⋃ ∞ S f i .
Since u ∈ B V ( Ω ) u\in\mathrm{BV}(\Omega) u ∈ BV ( Ω ) and f i ∈ B V l o c ( Ω ) f_i\in\mathrm{BV}_{\mathrm{loc}}(\Omega) f i ∈ BV loc ( Ω ) , the scalar BV rectifiability theorem [13, Theorem 3.78] implies that Γ \Gamma Γ is countably H n − 1 \mathcal{H}^{n-1} H n − 1 -rectifiable. Let n n n be a Borel map orienting Γ \Gamma Γ . Applying the interior trace theorem to u u u and each f i f_i f i gives us an H n − 1 \mathcal{H}^{n-1} H n − 1 -negligible set N ⊂ Γ \mathcal{N}\subset\Gamma N ⊂ Γ such that the one sided traces u n ± ( x ) u_n^\pm(x) u n ± ( x ) of u u u and ( f i ) n ± ( x ) (f_i)_n^\pm(x) ( f i ) n ± ( x ) (for any i i i ) exist at every x ∈ Γ ∖ N x\in\Gamma\setminus\mathcal{N} x ∈ Γ ∖ N , and are Borel.
Let x 0 ∈ Ω ∖ N x_0\in\Omega\setminus\mathcal{N} x 0 ∈ Ω ∖ N . For the following argument, we set B r = B ( x 0 , r ) B_r=B(x_0,r) B r = B ( x 0 , r ) in the case x 0 ∉ Γ x_0\notin\Gamma x 0 ∈ / Γ , and set B r B_r B r to be either half-ball B n ( x 0 ) ± ( x 0 , r ) B_{n(x_0)}^\pm(x_0,r) B n ( x 0 ) ± ( x 0 , r ) if x 0 ∈ Γ x_0\in\Gamma x 0 ∈ Γ . Additionally, we denote the trace (corresponding to B r B_r B r ) of u u u by τ \tau τ , and the trace of any f i f_i f i by τ i \tau_i τ i . Now, because
∣ v N ( x ) − min i ≤ N τ i ∣ ≤ ∑ i = 1 N ∣ f i ( x ) − τ i ∣ for any x ∈ Ω \left|v_N(x)-\min_{i\leq N}\tau_i\right|\leq\sum_{i=1}^{N}|f_i(x)-\tau_i|\qquad\text{for any }x\in\Omega v N ( x ) − i ≤ N min τ i ≤ i = 1 ∑ N ∣ f i ( x ) − τ i ∣ for any x ∈ Ω
we get
\lim_{r\to0^+}\fint_{B_r}\left|v_N-\min_{i\leq N}\tau_i\right|\,d\mathcal{L}^n=0.
Thus taking the limit of the average value of both sides of the inequality (29) over B r B_r B r gives us
0 ≤ min i ≤ N τ i ≤ τ M for N ≥ N M and M ∈ N , 0\leq\min_{i\leq N}\tau_i\leq\frac{\tau}{M}\qquad\text{for }N\geq N_M\text{ and }M\in\mathbb{N}, 0 ≤ i ≤ N min τ i ≤ M τ for N ≥ N M and M ∈ N ,
and hence inf i τ i = 0 \inf_i \tau_i = 0 inf i τ i = 0 . This provides us with a sequence { i j } \{i_j\} { i j } such that τ i j < 2 − j \tau_{i_j} < 2^{-j} τ i j < 2 − j for each j ∈ N j \in\mathbb{N} j ∈ N , and because
δ ( y i , y j ) ≤ τ i + τ j for any i , j ∈ N , \delta(y_i,y_j) \leq\tau_i+\tau_j \qquad\text{for any } i,j \in\mathbb{N}, δ ( y i , y j ) ≤ τ i + τ j for any i , j ∈ N ,
we get that the subsequence { y i j } \{y_{i_j}\} { y i j } is Cauchy. In particular, since Y Y Y is complete, this implies the existence of a point y 0 ∈ Y y_0 \in Y y 0 ∈ Y such that y i j → y 0 y_{i_j} \to y_0 y i j → y 0 .
Thus
\lim_{r\to0+} \fint_{B_r} \delta(w,y_0)\,d\mathcal{L}^n \leq\tau_{i_j}+\delta(y_{i_j},y_0) \longrightarrow0 \qquad\text{as } j\to\infty.
Therefore if x 0 ∉ Γ x_0 \notin\Gamma x 0 ∈ / Γ , i.e., the approximate limit of u u u and of all the f i f_i f i exist at x 0 x_0 x 0 , then the approximate limit of w w w exists at x 0 x_0 x 0 , and in particular, S w S_w S w is contained in the rectifiable set Γ \Gamma Γ . Therefore, S w S_w S w is H n − 1 \mathcal{H}^{n-1} H n − 1 -rectifiable. Moreover, we have shown that the one-sided traces w + ( x 0 ) w^+(x_0) w + ( x 0 ) and w − ( x 0 ) w^-(x_0) w − ( x 0 ) exist at any x 0 ∈ Γ ∖ N x_0 \in\Gamma\setminus\mathcal{N} x 0 ∈ Γ ∖ N . Enlarging N \mathcal{N} N if necessary, assume it is Borel and set G : = S w ∖ N G := S_w \setminus\mathcal{N} G := S w ∖ N . By the triangle inequality and uniqueness of scalar traces,
δ ( w ± ( x ) , y i ) = ( f i ) n ± ( x ) for x ∈ S w ∖ N , i ∈ N . \delta\left(w^\pm(x),y_i\right)=(f_i)^\pm_{\mathbf{n}}(x) \qquad\text{for } x\in S_w\setminus\mathcal{N},\ i\in\mathbb{N}. δ ( w ± ( x ) , y i ) = ( f i ) n ± ( x ) for x ∈ S w ∖ N , i ∈ N .
Since the metric balls around the countable dense set { y i } \{y_i\} { y i } generate the Borel σ \sigma σ -algebra of Y Y Y , the Borel measurability of the scalar traces implies w ± w^\pm w ± are Borel on S w ∖ N S_w\setminus\mathcal{N} S w ∖ N . Extend both maps by y 1 y_1 y 1 on S w ∩ N S_w\cap\mathcal{N} S w ∩ N and restrict n \mathbf{n} n to S w S_w S w .
Finally, the traces are distinct on S w ∖ N S_w\setminus\mathcal{N} S w ∖ N . Indeed, if they coincided, then combining the two half-ball limits would give a full-ball average limit, contradicting membership in S w S_w S w . □
The following theorem shows that metric space valued BV-functions on bounded open sets have boundary traces defined almost everywhere if the boundary is Lipschitz. This theorem motivates our notion of a filling (defined in the next section) between two metric space valued BV-functions.
Recall that a subset U ⊂ R n U \subset\mathbb{R}^n U ⊂ R n has Lipschitz boundary if for every point x ∈ ∂ U x \in\partial U x ∈ ∂ U there exists an open ball B r ( x ) B_r(x) B r ( x ) and a hyperplane P P P through x x x , such that B r ( x ) ∩ ∂ U B_r(x)\cap\partial U B r ( x ) ∩ ∂ U is the graph of some Lipschitz function over P P P .
Theorem 17 (Existence of the boundary trace). Let Ω ⊂ R n \Omega\subset\mathbb{R}^n Ω ⊂ R n be a bounded, open, connected set with Lipschitz boundary ∂ Ω \partial\Omega ∂ Ω and let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete separable metric space. If w ∈ BV ( Ω ; Y ) w \in\operatorname{BV}(\Omega;Y) w ∈ BV ( Ω ; Y ) then for H n − 1 \mathcal{H}^{n-1} H n − 1 -a.e. x 0 ∈ ∂ Ω x_0 \in\partial\Omega x 0 ∈ ∂ Ω there exists a w ∣ ∂ Ω ( x 0 ) ∈ Y w|_{\partial\Omega}(x_0) \in Y w ∣ ∂ Ω ( x 0 ) ∈ Y such that
\lim_{r\to0+} \fint_{\Omega\cap B(x_0,r)} \delta\left(w,w|_{\partial\Omega}(x_0)\right)\,d\mathcal{L}^n=0.
Proof. Define f i f_i f i and v N v_N v N as in the preceding theorem. By Step 1 of its proof, there exists a nonnegative u ∈ BV ( Ω ) u \in\operatorname{BV}(\Omega) u ∈ BV ( Ω ) such that, for every M ∈ N M \in\mathbb{N} M ∈ N , we have M v N ≤ u Mv_N \leq u M v N ≤ u for L n \mathcal{L}^n L n -almost everywhere. for all sufficiently large N N N .
By the scalar boundary trace theorem [13, Theorem 3.87], u u u and all of the f i f_i f i have finite boundary one-sided approximate limits outside of a common H n − 1 \mathcal{H}^{n-1} H n − 1 -negligible subset of ∂ Ω \partial\Omega ∂ Ω .
At each remaining boundary point x 0 x_0 x 0 , apply the reconstruction argument from Step 2 of the proof of Theorem 16 with B r : = Ω ∩ B ( x 0 , r ) B_r := \Omega\cap B(x_0,r) B r := Ω ∩ B ( x 0 , r ) . This gives a point w ∣ ∂ Ω ( x 0 ) ∈ Y w|_{\partial\Omega}(x_0) \in Y w ∣ ∂ Ω ( x 0 ) ∈ Y satisfying
\lim_{r\to0+} \fint_{\Omega\cap B(x_0,r)} \delta\left(w,w|_{\partial\Omega}(x_0)\right)\,d\mathcal{L}^n=0.
This concludes the proof. □
The Volume Exchange Metric and Dissimilarity
In this section, we define three notions of piecewise constant (PC) fillings between two piecewise constant functions p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y . After defining standard piecewise constant (PC) fillings between p p p and q q q , we will define two types of weak PC fillings. Our weakest type of PC filling (type-2) will only need to preserve distances between values corresponding to adjacent level-sets of our trace boundary condition, whereas type-1 PC fillings will need to preserve distances between all level sets. As explained below, these will correspond to the two notions of cellular fillings used to define the one-to-one volume exchange metric and many-to-many volume exchange dissimilarity in the introduction.
We say that a function w : Ω → Y w:\Omega\to Y w : Ω → Y is piecewise constant in Ω \Omega Ω if there exists a Caccioppoli partition { E α } α ∈ A \{E_\alpha\}_{\alpha\in A} { E α } α ∈ A of Ω \Omega Ω and a function y : A → Y y:A\to Y y : A → Y such that for each α ∈ A \alpha\in A α ∈ A , w ( x ) = y α w(x)=y_\alpha w ( x ) = y α for L n \mathcal{L}^n L n -a.e. x ∈ E α x\in E_\alpha x ∈ E α , and
∑ α ≠ β δ ( y α , y β ) H n − 1 ( Ω ∩ ∂ ∗ E α ∩ ∂ ∗ E β ) < + ∞ . \sum_{\alpha\ne\beta}\delta(y_\alpha,y_\beta)\mathcal{H}^{n-1}(\Omega\cap\partial^*E_\alpha\cap\partial^*E_\beta)<+\infty. α = β ∑ δ ( y α , y β ) H n − 1 ( Ω ∩ ∂ ∗ E α ∩ ∂ ∗ E β ) < + ∞.
Definition 18 (Piecewise constant filling). Given p , q ∈ PC ( Ω ; Y ) p,q\in\operatorname{PC}(\Omega;Y) p , q ∈ PC ( Ω ; Y ) , a piecewise constant (PC) filling between p p p and q q q is a piecewise constant function w : Ω × I → Y w:\Omega\times I\to Y w : Ω × I → Y such that
w ∣ Ω × 0 ( x , 0 ) = p ( x ) and w ∣ Ω × 1 ( x , 1 ) = q ( x ) for L n -a.e. x ∈ Ω . (30) w|_{\Omega\times0}(x,0)=p(x)\quad\text{and}\quad w|_{\Omega\times1}(x,1)=q(x)\quad\text{for }\mathcal{L}^n\text{-a.e. }x\in\Omega. \tag*{(30)} w ∣ Ω × 0 ( x , 0 ) = p ( x ) and w ∣ Ω × 1 ( x , 1 ) = q ( x ) for L n -a.e. x ∈ Ω. (30)
We denote the family of all fillings between p p p and q q q by F ( p , q ) \mathrm{F}(p,q) F ( p , q ) .
The following notion will be used to define our weakest type of PC filling. A function κ : im p → im p \kappa:\operatorname{im}p\to\operatorname{im}p κ : im p → im p is called a coarsening map for p p p if
δ ( κ ( y ) , κ ( y ′ ) ) = δ ( y , y ′ ) for all y , y ′ ∈ Y such that H n − 1 ( ∂ ∗ { p = y } ∩ ∂ ∗ { p = y ′ } ) > 0. \delta(\kappa(y),\kappa(y'))=\delta(y,y')\quad\text{for all }y,y'\in Y\text{ such that }\mathcal{H}^{n-1}(\partial^*\{p=y\}\cap\partial^*\{p=y'\})>0. δ ( κ ( y ) , κ ( y ′ )) = δ ( y , y ′ ) for all y , y ′ ∈ Y such that H n − 1 ( ∂ ∗ { p = y } ∩ ∂ ∗ { p = y ′ }) > 0.
With any coarsening map κ \kappa κ of p p p , one can define a new piecewise constant function κ ∘ p \kappa\circ p κ ∘ p which we call a coarsening of p p p . Denote the collection of coarsenings of p p p by C ( p ) \mathcal{C}(p) C ( p ) . A level-set of κ ∘ p \kappa\circ p κ ∘ p is the union of non-adjacent level-sets of p p p .
Definition 19 (Weak piecewise constant filling). Let p , q ∈ PC ( Ω ; Y ) p,q\in\operatorname{PC}(\Omega;Y) p , q ∈ PC ( Ω ; Y ) and w ∈ PC ( Ω × I ; Y ) w\in\operatorname{PC}(\Omega\times I;Y) w ∈ PC ( Ω × I ; Y ) . If there exists an isometry ψ : Y → Y \psi:Y\to Y ψ : Y → Y such that w w w is a filling between p p p and ψ ∘ q \psi\circ q ψ ∘ q , then w w w is called a weak type-1 PC filling between p p p and q q q . If there exists coarsening maps κ 0 \kappa_0 κ 0 and κ 1 \kappa_1 κ 1 for p p p and q q q such that w w w is a weak type-1 filling between κ 0 ∘ p \kappa_0\circ p κ 0 ∘ p and κ 1 ∘ q \kappa_1\circ q κ 1 ∘ q , then w w w is called a weak type-2 PC filling between p p p and $q.
For t ∈ { 1 , 2 } t\in\{1,2\} t ∈ { 1 , 2 } , we let F ( t ) ( p , q ) \mathrm{F}^{(t)}(p,q) F ( t ) ( p , q ) denote the set of all weak type-t t t piecewise constant fillings between p p p and q q q .
Suppose that Y Y Y is a complete, separable metric space and Ω \Omega Ω is a bounded, connected open subset of R n \mathbb{R}^n R n with Lipschitz boundary. Whenever w ∈ BV ( Ω × I ; Y ) w\in\operatorname{BV}(\Omega\times I;Y) w ∈ BV ( Ω × I ; Y ) Theorem 16 tells us that there exists a Borel map n w : S w → S n n_w:S_w\to S^n n w : S w → S n where n w ( x ) n_w(x) n w ( x ) is normal to the approximate tangent space Tan n ( H n ⌞ S w ) \operatorname{Tan}^n(\mathcal{H}^n\llcorner S_w) Tan n ( H n └ S w ) of S w S_w S w . The tangential Jacobian J S w π J^{S_w}\pi J S w π of the orthogonal projection π : R n × R → R n \pi:\mathbb{R}^{n}\times\mathbb{R}\to\mathbb{R}^{n} π : R n × R → R n is given by ∣ ⟨ v , n w ( x ) ⟩ ∣ |\langle v,n_w(x)\rangle| ∣ ⟨ v , n w ( x )⟩ ∣ for H n \mathcal{H}^{n} H n a.e. x ∈ S w x\in S_w x ∈ S w . By the generalized area formula (see [14, 3.2.22]),
Figure 5. The disk Ω \Omega Ω on the left is the domain of a piecewise constant function p p p whose image consists of the 5 points on the right. The collection of cells of a single color depicts the level set of p p p at the point with the same color. The isometry ψ \psi ψ used within a weak type 1 filling must preserve the lengths of all line-segments. However within a weak type 2 filling, ψ ∘ κ \psi\circ\kappa ψ ∘ κ only needs to preserve the lengths of the solid line-segments because the cells corresponding to the dashed lines are not adjacent.
E δ [ w ] = ∫ Ω × 0 ( ∫ S w ∩ π − 1 ( x ) δ ( w + , w − ) d H 0 ) d L n ( x ) = ∫ S w δ ( w + , w − ) ∣ ⟨ v , n ⟩ ∣ d H n . (31) \mathcal{E}_{\delta}[w]=\int_{\Omega\times0}\left(\int_{S_w\cap\pi^{-1}(x)}\delta(w^{+},w^{-})\,d\mathcal{H}^{0}\right)d\mathcal{L}^{n}(x)=\int_{S_w}\delta(w^{+},w^{-})|\langle v,n\rangle|\,d\mathcal{H}^{n}. \tag*{(31)} E δ [ w ] = ∫ Ω × 0 ( ∫ S w ∩ π − 1 ( x ) δ ( w + , w − ) d H 0 ) d L n ( x ) = ∫ S w δ ( w + , w − ) ∣ ⟨ v , n ⟩ ∣ d H n . (31)
By minimizing E δ \mathcal{E}_{\delta} E δ over our three different types of fillings, we are able to equip PC ( Ω ; Y ) \operatorname{PC}(\Omega;Y) PC ( Ω ; Y ) with the projected surface energy d V d_{\mathrm V} d V , the volume exchange pseudometric d V 1 d_{\mathrm V}^{1} d V 1 , and the volume exchange dissimilarity d V 2 d_{\mathrm V}^{2} d V 2 . They are defined, respectively, by
d V ( p , q ) : = inf w ∈ F ( p , q ) E δ [ w ] , d V 1 ( p , q ) : = inf w ∈ F ( 1 ) ( p , q ) E δ [ w ] , d V 2 ( p , q ) : = inf w ∈ F ( 2 ) ( p , q ) E δ [ w ] . (32) d_{\mathrm V}(p,q):=\inf_{w\in\mathcal{F}(p,q)}\mathcal{E}_{\delta}[w],\qquad d_{\mathrm V}^{1}(p,q):=\inf_{w\in\mathcal{F}^{(1)}(p,q)}\mathcal{E}_{\delta}[w],\qquad d_{\mathrm V}^{2}(p,q):=\inf_{w\in\mathcal{F}^{(2)}(p,q)}\mathcal{E}_{\delta}[w]. \tag*{(32)} d V ( p , q ) := w ∈ F ( p , q ) inf E δ [ w ] , d V 1 ( p , q ) := w ∈ F ( 1 ) ( p , q ) inf E δ [ w ] , d V 2 ( p , q ) := w ∈ F ( 2 ) ( p , q ) inf E δ [ w ] . (32)
for all p , q ∈ PC ( Ω ; Y ) p,q\in\operatorname{PC}(\Omega;Y) p , q ∈ PC ( Ω ; Y ) .
Remark 20. Directly from the definitions we can see that for any two piecewise constant functions p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y ,
F ( p , q ) ⊂ F ( 1 ) ( p , q ) ⊂ F ( 2 ) ( p , q ) , \mathcal{F}(p,q)\subset\mathcal{F}^{(1)}(p,q)\subset\mathcal{F}^{(2)}(p,q), F ( p , q ) ⊂ F ( 1 ) ( p , q ) ⊂ F ( 2 ) ( p , q ) ,
and hence , d V ≥ d V 1 ≥ d V 2 d_{\mathrm V}\ge d_{\mathrm V}^{1}\ge d_{\mathrm V}^{2} d V ≥ d V 1 ≥ d V 2 .
Before we prove Theorem 6, let us state an important corollary of it, which says that these three “metrics” are given to us by minimizing the L 1 L^{1} L 1 -norm of δ ( f , g ) \delta(f,g) δ ( f , g ) , where f f f and g g g are obtained by post-composing p p p and q q q with the functions from Y Y Y to Y Y Y we used to define our fillings.
Corollary 21. Let ( Y , δ ) (Y,\delta) ( Y , δ ) be a complete, separable metric space. If p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y are piecewise constant on a bounded, connected, open domain Ω ⊂ R n \Omega\subset\mathbb{R}^{n} Ω ⊂ R n then
d V ( p , q ) = ∫ Ω δ ( p , q ) d L n d_{V}(p,q)=\int_{\Omega}\delta(p,q)\,d\mathcal{L}^{n} d V ( p , q ) = ∫ Ω δ ( p , q ) d L n
d V 1 ( p , q ) = inf ψ 1 , ψ 2 ∈ Iso ( Y ) ∫ Ω δ ( ψ 1 ∘ p , ψ 2 ∘ q ) d L n d_{V}^{1}(p,q)=\inf_{\psi_{1},\psi_{2}\in\operatorname{Iso}(Y)}\int_{\Omega}\delta(\psi_{1}\circ p,\psi_{2}\circ q)\,d\mathcal{L}^{n} d V 1 ( p , q ) = ψ 1 , ψ 2 ∈ Iso ( Y ) inf ∫ Ω δ ( ψ 1 ∘ p , ψ 2 ∘ q ) d L n
d V 2 ( p , q ) = inf ψ 1 , ψ 2 ∈ Iso ( Y ) inf p ′ ∈ C ( p ) , q ′ ∈ C ( q ) ∫ Ω δ ( ψ 1 ∘ p ′ , ψ 2 ∘ q ′ ) d L n . d_{V}^{2}(p,q)=\inf_{\psi_{1},\psi_{2}\in\operatorname{Iso}(Y)}\inf_{\substack{p'\in\mathcal{C}(p),\\q'\in\mathcal{C}(q)}}\int_{\Omega}\delta(\psi_{1}\circ p',\psi_{2}\circ q')\,d\mathcal{L}^{n}. d V 2 ( p , q ) = ψ 1 , ψ 2 ∈ Iso ( Y ) inf p ′ ∈ C ( p ) , q ′ ∈ C ( q ) inf ∫ Ω δ ( ψ 1 ∘ p ′ , ψ 2 ∘ q ′ ) d L n .
Proof of Theorem 6. We will first show that for any w ∈ PC ( Ω × I ; Y ) w\in\operatorname{PC}(\Omega\times I;Y) w ∈ PC ( Ω × I ; Y ) ,
∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) = ∫ S w δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n . (33) \int_{\Omega}|Dw_{x}|(I)\,d\mathcal{L}^{n}(x)=\int_{S_{w}}\delta(w^{+},w^{-})|\langle v,n_{w}\rangle|\,d\mathcal{H}^{n}. \tag*{(33)} ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) = ∫ S w δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n . (33)
Theorem 16, tells us that the approximate discontinuity set S w S_{w} S w of w w w is countably H n \mathcal{H}^{n} H n -rectifiable, and has an orienting Borel map n w : S w → S n n_{w}:S_{w}\to S^{n} n w : S w → S n such that the one sided approximate limits of w w w exist H n \mathcal{H}^{n} H n -a.e. on S w S_{w} S w . Moreover, it defines Borel maps w + , w − : S w → Y w^{+},w^{-}:S_{w}\to Y w + , w − : S w → Y . Therefore, by the generalized area formula,
∫ S w δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n = ∫ Ω ∑ { t : ( x , t ) ∈ S w } δ ( w + ( x , t ) , w − ( x , t ) ) d L n ( x ) . \int_{S_{w}}\delta(w^{+},w^{-})|\langle v,n_{w}\rangle|\,d\mathcal{H}^{n}=\int_{\Omega}\sum_{\{t:(x,t)\in S_{w}\}}\delta(w^{+}(x,t),w^{-}(x,t))\,d\mathcal{L}^{n}(x). ∫ S w δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n = ∫ Ω { t : ( x , t ) ∈ S w } ∑ δ ( w + ( x , t ) , w − ( x , t )) d L n ( x ) .
It remains to show
∣ D w x ∣ ( I ) = ∑ { t : ( x , t ) ∈ S w } δ ( w + ( x , t ) , w − ( x , t ) ) for L n -a.e. x ∈ Ω . |Dw_{x}|(I)=\sum_{\{t:(x,t)\in S_{w}\}}\delta(w^{+}(x,t),w^{-}(x,t))\quad\text{for }\mathcal{L}^{n}\text{-a.e. }x\in\Omega. ∣ D w x ∣ ( I ) = { t : ( x , t ) ∈ S w } ∑ δ ( w + ( x , t ) , w − ( x , t )) for L n -a.e. x ∈ Ω.
Let { y i } \{y_{i}\} { y i } be a countable dense subset of Y Y Y and define f i : = δ ( w , y i ) f_{i}:=\delta(w,y_{i}) f i := δ ( w , y i ) for each i i i . Since w ∈ PC ( Ω ; Y ) w\in\operatorname{PC}(\Omega;Y) w ∈ PC ( Ω ; Y ) , each f i f_{i} f i is a piecewise-constant scalar-valued BV function. The reverse triangle inequality and the existence of one-sided traces w ± w^{\pm} w ± for w w w from Theorem 16 implies
f i ± ( x ) = δ ( w ± , y i ) for L n -a.e. x ∈ Ω . f_{i}^{\pm}(x)=\delta(w^{\pm},y_{i})\quad\text{for }\mathcal{L}^{n}\text{-a.e. }x\in\Omega. f i ± ( x ) = δ ( w ± , y i ) for L n -a.e. x ∈ Ω.
By [13, Theorem 3.108, Remark 3.109] for almost every $x\in\Omega,
∣ D ( f i ) x ∣ = ∑ { t : ( x , t ) ∈ S w } ∣ δ ( w + ( x , t ) , y i ) − δ ( w − ( x , t ) , y i ) ∣ δ t for all i , |D(f_{i})_{x}|=\sum_{\{t:(x,t)\in S_{w}\}}\left|\delta(w^{+}(x,t),y_{i})-\delta(w^{-}(x,t),y_{i})\right|\delta_{t}\quad\text{for all }i, ∣ D ( f i ) x ∣ = { t : ( x , t ) ∈ S w } ∑ δ ( w + ( x , t ) , y i ) − δ ( w − ( x , t ) , y i ) δ t for all i ,
where δ t \delta_{t} δ t denotes the Dirac delta measure supported on $t.
By Lemma 11, (\mathcal{L}^{n}\mathbin{\vrule height 1.4ex depth -0.4ex width 0.07em\vrule height 0.07ex depth -0.02ex width 0.7em}\Omega) -almost every vertical restriction w x w_{x} w x of w w w is a BV-curve. Additionally, for any such x x x ,
∣ D w x ∣ = ⋁ i ∣ D ( f i ) x ∣ . |Dw_{x}|=\bigvee_{i}|D(f_{i})_{x}|. ∣ D w x ∣ = i ⋁ ∣ D ( f i ) x ∣.
Indeed, in the last part of the proof of Lemma 11, we show that ∣ D w x ∣ ≤ ⋁ i ∣ D ( f i ) x ∣ |Dw_{x}|\leq\bigvee_{i}|D(f_{i})_{x}| ∣ D w x ∣ ≤ ⋁ i ∣ D ( f i ) x ∣ . Furthermore, since φ i ( y ) : = δ ( y , y i ) \varphi_{i}(y):=\delta(y,y_{i}) φ i ( y ) := δ ( y , y i ) is 1-Lipschitz and ( f i ) x = φ i ∘ w x (f_{i})_{x}=\varphi_{i}\circ w_{x} ( f i ) x = φ i ∘ w x , the definition of ∣ D w x ∣ |Dw_{x}| ∣ D w x ∣ gives us ∣ D ( f i ) x ∣ ≤ ∣ D w x ∣ |D(f_{i})_{x}|\leq|Dw_{x}| ∣ D ( f i ) x ∣ ≤ ∣ D w x ∣ .
Thus
∣ D w x ∣ ( I ) = ( ⋁ i ∣ D ( f i ) x ∣ ) ( I ) = ∑ { t : ( x , t ) ∈ S w } sup i ∣ δ ( w + ( x , t ) , y i ) − δ ( w − ( x , t ) , y i ) ∣ ; |Dw_{x}|(I)=\left(\bigvee_{i}|D(f_{i})_{x}|\right)(I)=\sum_{\{t:(x,t)\in S_{w}\}}\sup_{i}\left|\delta(w^{+}(x,t),y_{i})-\delta(w^{-}(x,t),y_{i})\right|; ∣ D w x ∣ ( I ) = ( i ⋁ ∣ D ( f i ) x ∣ ) ( I ) = { t : ( x , t ) ∈ S w } ∑ i sup δ ( w + ( x , t ) , y i ) − δ ( w − ( x , t ) , y i ) ;
and because δ ( y , y ′ ) = sup i ∣ δ ( y , y i ) − δ ( y ′ , y i ) ∣ \delta(y,y')=\sup_i\lvert\delta(y,y_i)-\delta(y',y_i)\rvert δ ( y , y ′ ) = sup i ∣ δ ( y , y i ) − δ ( y ′ , y i )∣ for any y , y ′ ∈ Y y,y'\in Y y , y ′ ∈ Y , we get that
∣ D w x ∣ ( I ) = ∑ { t : ( x , t ) ∈ S w } δ ( w + ( x , t ) , w − ( x , t ) ) . \lvert Dw_x\rvert(I)=\sum_{\{t:(x,t)\in S_w\}}\delta\left(w^+(x,t),w^-(x,t)\right). ∣ D w x ∣ ( I ) = { t : ( x , t ) ∈ S w } ∑ δ ( w + ( x , t ) , w − ( x , t ) ) .
Therefore,
∫ S w δ ( w + , w − ) ∣ ⟨ v , n w ⟩ ∣ d H n = ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) . \int_{S_w}\delta\left(w^+,w^-\right)\lvert\langle v,n_w\rangle\rvert\,d\mathcal{H}^n=\int_{\Omega}\lvert Dw_x\rvert(I)\,d\mathcal{L}^n(x). ∫ S w δ ( w + , w − ) ∣⟨ v , n w ⟩∣ d H n = ∫ Ω ∣ D w x ∣ ( I ) d L n ( x ) .
The step function w ∗ w^* w ∗ (defined in Lemma 15 ) corresponding to the piecewise constant trace boundaries p p p and q q q , is piecewise constant, and hence belongs to F ( p , q ) \mathrm{F}(p,q) F ( p , q ) . The proof of Lemma 15 shows that any step function obtains the minimum in the statement of Theorem 13 . Therefore, restricting the minimization to F ( p , q ) \mathrm{F}(p,q) F ( p , q ) leaves the minimum unchanged, and our conclusion follows from equality (33) . □
Next, we relate these definitions to those given in the introduction.
Proposition 22. Let Y Y Y be the discrete metric space on N \mathbb{N} N and let P = { E α ′ } α ∈ A \mathcal{P}=\{E'_\alpha\}_{\alpha\in A} P = { E α ′ } α ∈ A and Q = { E β ′ ′ } β ∈ B \mathcal{Q}=\{E''_\beta\}_{\beta\in B} Q = { E β ′′ } β ∈ B be cell structures on Ω \Omega Ω where A , B ⊂ N A,B\subset\mathbb{N} A , B ⊂ N satisfy ∣ N ∖ A ∣ , ∣ N ∖ B ∣ = ∞ \lvert\mathbb{N}\setminus A\rvert,\lvert\mathbb{N}\setminus B\rvert=\infty ∣ N ∖ A ∣ , ∣ N ∖ B ∣ = ∞ . If p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y are defined by setting p ( E α ′ ) = α p(E'_\alpha)=\alpha p ( E α ′ ) = α and q ( E β ′ ′ ) = β q(E''_\beta)=\beta q ( E β ′′ ) = β for all α ∈ A \alpha\in A α ∈ A and β ∈ B \beta\in B β ∈ B then
d V 1 ( P , Q ) = d V 1 ( p , q ) d_{\mathrm{V}}^1(\mathcal{P},\mathcal{Q})=d_{\mathrm{V}}^1(p,q) d V 1 ( P , Q ) = d V 1 ( p , q ) and
d V 2 ( P , Q ) = d V 2 ( p , q ) . d_{\mathrm{V}}^2(\mathcal{P},\mathcal{Q})=d_{\mathrm{V}}^2(p,q). d V 2 ( P , Q ) = d V 2 ( p , q ) . Proof. It suffices to show that for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } and every W ∈ F i ( P , Q ) \mathcal{W}\in\mathrm{F}^i(\mathcal{P},\mathcal{Q}) W ∈ F i ( P , Q ) there is a w ∈ F i ( p , q ) w\in\mathrm{F}^i(p,q) w ∈ F i ( p , q ) with
E ( W ) = E δ [ w ] \mathcal{E}(\mathcal{W})=\mathcal{E}_{\delta}[w] E ( W ) = E δ [ w ] and vice versa.
We begin with the case i = 1 i=1 i = 1 . First, let W ∈ F 1 ( P , Q ) \mathcal{W}\in\mathrm{F}^1(\mathcal{P},\mathcal{Q}) W ∈ F 1 ( P , Q ) and denote its cells by { E γ } γ ∈ C \{E_\gamma\}_{\gamma\in C} { E γ } γ ∈ C . For convenience, we treat P \mathcal{P} P and Q \mathcal{Q} Q as partitions of Ω × { 0 } \Omega\times\{0\} Ω × { 0 } and Ω × { 1 } \Omega\times\{1\} Ω × { 1 } , respectively. By definition, the cells of P \mathcal{P} P are — up H n \mathcal{H}^n H n -negligible sets — the H n \mathcal{H}^n H n -non-negligible intersections ∂ ∗ E ∩ Ω × { 0 } \partial^*E\cap\Omega\times\{0\} ∂ ∗ E ∩ Ω × { 0 } for cells E ∈ W E\in\mathcal{W} E ∈ W , and analogously for Q \mathcal{Q} Q . Say that a cell E E E of W \mathcal{W} W corresponds to a cell E ′ E' E ′ of P \mathcal{P} P or Q \mathcal{Q} Q if H n ( ∂ ∗ E ∩ E ′ ) > 0 \mathcal{H}^n(\partial^*E\cap E')>0 H n ( ∂ ∗ E ∩ E ′ ) > 0 . We may reindex the cells of W \mathcal{W} W if necessary so that E α E_\alpha E α corresponds to E α ′ E'_\alpha E α ′ for all α ∈ A \alpha\in A α ∈ A , where we are implicitly using that ∣ N ∖ A ∣ = ∞ \lvert\mathbb{N}\setminus A\rvert=\infty ∣ N ∖ A ∣ = ∞ . Choose a permutation ϕ : Y → Y \phi:Y\to Y ϕ : Y → Y so that E ϕ − 1 ( β ) E_{\phi^{-1}(\beta)} E ϕ − 1 ( β ) is the cell of W \mathcal{W} W corresponding to E β ′ ′ E''_\beta E β ′′ for all β ∈ B \beta\in B β ∈ B .
Define w : Ω × I → Y w:\Omega\times I\to Y w : Ω × I → Y by w ( E γ ) = γ w(E_\gamma)=\gamma w ( E γ ) = γ . By construction, w ∣ Ω × 0 = p w|_{\Omega\times0}=p w ∣ Ω × 0 = p and w ∣ Ω × 1 = ϕ − 1 ∘ q w|_{\Omega\times1}=\phi^{-1}\circ q w ∣ Ω × 1 = ϕ − 1 ∘ q , That is, w w w defines a weak type-1 PC filling between p p p and q q q . Comparing Equations (1) and (4) , we have that
E ( W ) = E δ [ w ] . \mathcal{E}(\mathcal{W})=\mathcal{E}_{\delta}[w]. E ( W ) = E δ [ w ] . On the other hand, let w ∈ F 1 ( p , q ) w\in\mathrm{F}^1(p,q) w ∈ F 1 ( p , q ) and let W \mathcal{W} W be the partition of Ω × I \Omega\times I Ω × I into level sets of w w w . By construction, W ∈ F 1 ( P , Q ) \mathcal{W}\in\mathrm{F}^1(\mathcal{P},\mathcal{Q}) W ∈ F 1 ( P , Q ) and
E ( W ) = E δ [ w ] . \mathcal{E}(\mathcal{W})=\mathcal{E}_{\delta}[w]. E ( W ) = E δ [ w ] . Now, let i = 2 i=2 i = 2 and W ∈ F 2 ( P , Q ) \mathcal{W}\in\mathrm{F}^2(\mathcal{P},\mathcal{Q}) W ∈ F 2 ( P , Q ) so W \mathcal{W} W is a type-1 cellular filling between coarsenings of P ′ \mathcal{P}' P ′ of P \mathcal{P} P and Q ′ \mathcal{Q}' Q ′ of Q \mathcal{Q} Q . Index the cells of P ′ \mathcal{P}' P ′ and Q ′ \mathcal{Q}' Q ′ by index sets A ′ ⊂ A A'\subset A A ′ ⊂ A and B ′ ⊂ B B'\subset B B ′ ⊂ B so the index
of a cell equals the indices of one of the constituent cells from the respective finer partition. Let p ′ : Ω → Y p' : \Omega\to Y p ′ : Ω → Y , q ′ : Ω → Y q' : \Omega\to Y q ′ : Ω → Y be as in the statement but for P ′ \mathcal{P}' P ′ and Q ′ \mathcal{Q}' Q ′ rather than P \mathcal{P} P and Q \mathcal{Q} Q . Then p ′ p' p ′ and q ′ q' q ′ are coarsenings of p p p and q q q , respectively. Applying the same argument as in the case i = 1 i=1 i = 1 produces a permutation ϕ : Y → Y \phi: Y \to Y ϕ : Y → Y and a PC filling w : Ω × ( 0 , 1 ) → Y w : \Omega\times(0,1) \to Y w : Ω × ( 0 , 1 ) → Y between p ′ p' p ′ and ϕ ∘ q ′ \phi\circ q' ϕ ∘ q ′ so that
E ( W ) = E δ [ w ] . \mathcal{E}(\mathcal{W})=\mathcal{E}_{\delta}[w]. E ( W ) = E δ [ w ] .
Since p ′ p' p ′ and q ′ q' q ′ are coarsenings of p p p and q q q , w w w is the desired weak type-2 PC filling between p p p and q q q . The argument for the other direction is identical to that for i = 1 i=1 i = 1 . □ \square □
The Discrete Volume Exchange Metric and Dissimilarity
Here, we define a discrete analog of the continuous volume exchange dissimilarities, prove their equality, and describe algorithms to compute them. Theorem 5 reduce these a priori continuous problems to discrete optimizations, and Theorem 27 converts the former into a linear assignment problem. We begin by reviewing the discrete analogue of the one-to-one volume exchange metric.
For convenience, take I , J ⊂ N I,J \subset\mathbb{N} I , J ⊂ N to be index sets. Let M = { U i } i ∈ I M=\{U_i\}_{i\in I} M = { U i } i ∈ I and N = { V j } j ∈ J N=\{V_j\}_{j\in J} N = { V j } j ∈ J be Caccioppoli partitions of an ambient space Ω ⊂ R n \Omega\subset\mathbb{R}^n Ω ⊂ R n , and PM ( I , J ) \operatorname{PM}(I,J) PM ( I , J ) be the collection of all partial matchings between them. By Definition 2 each index in I ∪ J I\cup J I ∪ J is seen exactly once in the partial matching. For the following definition, let U ∗ , V ∗ = ∅ U_*,V_*=\varnothing U ∗ , V ∗ = ∅ .
As in the introduction, recall that the discrete one-to-one volume exchange metric between cell structures P \mathcal{P} P and Q \mathcal{Q} Q is defined as
d V 1 ( P , Q ) : = 1 2 min R ∈ PM ( P , Q ) ∑ ( E , F ) ∈ R L n ( E △ F ) . d_{\mathrm{V}}^1(\mathcal{P},\mathcal{Q}) := \frac{1}{2}\min_{\mathcal{R}\in\operatorname{PM}(\mathcal{P},\mathcal{Q})}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^n(E\triangle F). d V 1 ( P , Q ) := 2 1 R ∈ PM ( P , Q ) min ( E , F ) ∈ R ∑ L n ( E △ F ) .
where we will justify that the minimum exists below.
Lemma 23. If ( Y , δ ) (Y,\delta) ( Y , δ ) is a countable discrete metric space and p , q ∈ PC ( Ω ; Y ) p,q\in\operatorname{PC}(\Omega;Y) p , q ∈ PC ( Ω ; Y ) , then
∫ Ω δ ( p , q ) d L n = 1 2 ∑ i ∈ Y L n ( { p = i } △ { q = i } ) . \int_{\Omega}\delta(p,q)\,d\mathcal{L}^n=\frac{1}{2}\sum_{i\in Y}\mathcal{L}^n(\{p=i\}\triangle\{q=i\}). ∫ Ω δ ( p , q ) d L n = 2 1 i ∈ Y ∑ L n ({ p = i } △ { q = i }) .
Proof. Our piecewise constant functions p p p and q q q provide us with two partitions P = { E i } \mathcal{P}=\{E_i\} P = { E i } and Q = { F i } \mathcal{Q}=\{F_i\} Q = { F i } of Ω \Omega Ω , given by the level sets E i : = p − 1 ( i ) E_i:=p^{-1}(i) E i := p − 1 ( i ) and F i : = q − 1 ( i ) F_i:=q^{-1}(i) F i := q − 1 ( i ) over all i ∈ Y i\in Y i ∈ Y . By definition, the nonempty elements of P \mathcal{P} P and Q \mathcal{Q} Q form cell structures on Ω \Omega Ω . With these partitions, observe that
∑ i ∈ Y ∫ E i δ ( p , q ) d L n = ∫ Ω δ ( p , q ) d L n = ∑ i ∈ Y ∫ F i δ ( p , q ) d L n . \sum_{i\in Y}\int_{E_i}\delta(p,q)\,d\mathcal{L}^n
=
\int_{\Omega}\delta(p,q)\,d\mathcal{L}^n
=
\sum_{i\in Y}\int_{F_i}\delta(p,q)\,d\mathcal{L}^n. i ∈ Y ∑ ∫ E i δ ( p , q ) d L n = ∫ Ω δ ( p , q ) d L n = i ∈ Y ∑ ∫ F i δ ( p , q ) d L n .
Since
∫ Ω δ ( p , q ) d L n = ∑ i , j ∈ Y δ ( i , j ) L n ( E i ∩ F j ) \int_{\Omega}\delta(p,q)\,d\mathcal{L}^n
=
\sum_{i,j\in Y}\delta(i,j)\mathcal{L}^n(E_i\cap F_j) ∫ Ω δ ( p , q ) d L n = i , j ∈ Y ∑ δ ( i , j ) L n ( E i ∩ F j )
it follows that
∫ E i δ ( p , q ) d L n = ∑ j ∈ q ( E i ) δ ( i , j ) L n ( E i ∩ F j ) . \int_{E_i}\delta(p,q)\,d\mathcal{L}^n
=
\sum_{j\in q(E_i)}\delta(i,j)\mathcal{L}^n(E_i\cap F_j). ∫ E i δ ( p , q ) d L n = j ∈ q ( E i ) ∑ δ ( i , j ) L n ( E i ∩ F j ) .
However, if j = i j=i j = i for j ∈ q ( E i ) j\in q(E_i) j ∈ q ( E i ) then δ ( i , j ) = 0 \delta(i,j)=0 δ ( i , j ) = 0 . Thus,
∑ j ∈ q ( E i ) δ ( i , j ) L n ( E i ∩ F j ) = L n ( E i ∖ F i ) . \sum_{j\in q(E_i)}\delta(i,j)\mathcal{L}^n(E_i\cap F_j)=\mathcal{L}^n(E_i\setminus F_i). j ∈ q ( E i ) ∑ δ ( i , j ) L n ( E i ∩ F j ) = L n ( E i ∖ F i ) .
So,
∫ Ω δ ( p , q ) d L n = 1 2 ( ∑ i ∈ Y ∫ E i δ ( p , q ) d L n + ∑ j ∈ Y ∫ F j δ ( p , q ) d L n ) = 1 2 ( ∑ i ∈ Y L n ( E i ∖ F i ) + ∑ j ∈ Y L n ( F j ∖ E j ) ) = 1 2 ∑ i ∈ Y ( L n ( E i ∖ F i ) + L n ( F i ∖ E i ) ) = 1 2 ∑ i ∈ Y L n ( E i △ F i ) . \begin{aligned}
\int_{\Omega}\delta(p,q)\,\mathrm{d}\mathcal{L}^n
&=\frac{1}{2}\left(\sum_{i\in Y}\int_{E_i}\delta(p,q)\,\mathrm{d}\mathcal{L}^n+\sum_{j\in Y}\int_{F_j}\delta(p,q)\,\mathrm{d}\mathcal{L}^n\right)\\
&=\frac{1}{2}\left(\sum_{i\in Y}\mathcal{L}^n(E_i\setminus F_i)+\sum_{j\in Y}\mathcal{L}^n(F_j\setminus E_j)\right)\\
&=\frac{1}{2}\sum_{i\in Y}\left(\mathcal{L}^n(E_i\setminus F_i)+\mathcal{L}^n(F_i\setminus E_i)\right)\\
&=\frac{1}{2}\sum_{i\in Y}\mathcal{L}^n(E_i\mathbin{\triangle}F_i).
\end{aligned} ∫ Ω δ ( p , q ) d L n = 2 1 i ∈ Y ∑ ∫ E i δ ( p , q ) d L n + j ∈ Y ∑ ∫ F j δ ( p , q ) d L n = 2 1 i ∈ Y ∑ L n ( E i ∖ F i ) + j ∈ Y ∑ L n ( F j ∖ E j ) = 2 1 i ∈ Y ∑ ( L n ( E i ∖ F i ) + L n ( F i ∖ E i ) ) = 2 1 i ∈ Y ∑ L n ( E i △ F i ) .
Proof of Theorem 5 . Let P = { E α ′ } α ∈ A \mathcal{P}=\{E'_{\alpha}\}_{\alpha\in A} P = { E α ′ } α ∈ A and Q = { E β ′ ′ } β ∈ B \mathcal{Q}=\{E''_{\beta}\}_{\beta\in B} Q = { E β ′′ } β ∈ B be cell structures on Ω \Omega Ω and denote by ( Y , δ ) (Y,\delta) ( Y , δ ) the discrete metric space on N \mathbb{N} N , where we have chosen the index sets A , B ⊂ N A,B\subset\mathbb{N} A , B ⊂ N so that ∣ N ∖ A ∣ = ∞ |\mathbb{N}\setminus A|=\infty ∣ N ∖ A ∣ = ∞ and ∣ N ∖ B ∣ = ∞ |\mathbb{N}\setminus B|=\infty ∣ N ∖ B ∣ = ∞ . Define piecewise constant functions p , q : Ω → Y p,q:\Omega\to Y p , q : Ω → Y by setting p ( E α ′ ) = α p(E'_{\alpha})=\alpha p ( E α ′ ) = α and q ( E β ′ ′ ) = β q(E''_{\beta})=\beta q ( E β ′′ ) = β for α ∈ A , β ∈ B \alpha\in A,\beta\in B α ∈ A , β ∈ B . By Proposition 22 it suffices to show that
d V i ( p , q ) = d D V i ( P , Q ) d_{\mathrm{V}}^i(p,q)=d_{\mathrm{DV}}^i(\mathcal{P},\mathcal{Q}) d V i ( p , q ) = d DV i ( P , Q )
for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } .
Proof that d D V 1 = d V 1 d_{\mathrm{DV}}^1=d_{\mathrm{V}}^1 d DV 1 = d V 1 . Let R ∈ P M ( P , Q ) \mathcal{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) and let f A : A → Y f_A:A\to Y f A : A → Y and f B : B → Y f_B:B\to Y f B : B → Y be injective functions with the following properties:
(i) f A ( α ) = f B ( β ) f_A(\alpha)=f_B(\beta) f A ( α ) = f B ( β ) if and only if ( E α ′ , E β ′ ′ ) ∈ R (E'_{\alpha},E''_{\beta})\in\mathcal{R} ( E α ′ , E β ′′ ) ∈ R ;
(ii) f A ( α ) ≠ f B ( β ) f_A(\alpha)\ne f_B(\beta) f A ( α ) = f B ( β ) for any β ∈ B \beta\in B β ∈ B if ( E α ′ , ∗ ) ∈ R (E'_{\alpha},*)\in\mathcal{R} ( E α ′ , ∗ ) ∈ R ;
(iii) f B ( β ) ≠ f A ( α ) f_B(\beta)\ne f_A(\alpha) f B ( β ) = f A ( α ) for any α ∈ A \alpha\in A α ∈ A if ( ∗ , E β ′ ′ ) ∈ R ( *,E''_{\beta})\in\mathcal{R} ( ∗ , E β ′′ ) ∈ R ;
• (iv)] ∣ N ∖ f A ( A ) ∣ , ∣ N ∖ f B ( B ) ∣ = ∞ |\mathbb{N}\setminus f_A(A)|,|\mathbb{N}\setminus f_B(B)|=\infty ∣ N ∖ f A ( A ) ∣ , ∣ N ∖ f B ( B ) ∣ = ∞ . Extend f A f_A f A and f B f_B f B to bijective functions from N \mathbb{N} N to N \mathbb{N} N . By construction, f A ∘ p , f B ∘ q ∈ PC ( Ω ; Y ) f_A \circ p, f_B \circ q \in\operatorname{PC}(\Omega;Y) f A ∘ p , f B ∘ q ∈ PC ( Ω ; Y ) . We have that
d V 1 ( p , q ) = d V 1 ( f A ∘ p , f B ∘ q ) = inf φ ∈ Iso ( Y ) ∫ Ω δ ( f A ∘ p , φ ∘ ( f B ∘ q ) ) d L n by Corollary 21 ≤ ∫ Ω δ ( f A ∘ p , Id Y ∘ ( f B ∘ q ) ) d L n = 1 2 ∑ i ∈ Y L n ( { f A ∘ p = i } △ { f B ∘ q = i } ) by Lemma 23 = 1 2 ∑ ( E , F ) ∈ R L n ( E △ F ) . \begin{aligned}
d_V^1(p,q) &= d_V^1(f_A\circ p,f_B\circ q)\\
&= \inf_{\varphi\in\operatorname{Iso}(Y)}\int_\Omega\delta(f_A\circ p,\varphi\circ(f_B\circ q))\,d\mathcal{L}^n &&\text{by Corollary 21}\\
&\le\int_\Omega\delta(f_A\circ p,\operatorname{Id}_Y\circ(f_B\circ q))\,d\mathcal{L}^n\\
&= \frac{1}{2}\sum_{i\in Y}\mathcal{L}^n(\{f_A\circ p=i\}\mathbin{\triangle}\{f_B\circ q=i\}) &&\text{by Lemma 23}\\
&= \frac{1}{2}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^n(E\mathbin{\triangle}F).
\end{aligned} d V 1 ( p , q ) = d V 1 ( f A ∘ p , f B ∘ q ) = φ ∈ Iso ( Y ) inf ∫ Ω δ ( f A ∘ p , φ ∘ ( f B ∘ q )) d L n ≤ ∫ Ω δ ( f A ∘ p , Id Y ∘ ( f B ∘ q )) d L n = 2 1 i ∈ Y ∑ L n ({ f A ∘ p = i } △ { f B ∘ q = i }) = 2 1 ( E , F ) ∈ R ∑ L n ( E △ F ) . by Corollary 21 by Lemma 23
Since this holds for all R ∈ PM ( P , Q ) \mathcal{R}\in\operatorname{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) , d V 1 ≤ d D V 1 d_V^1\le d_{\mathrm{DV}}^1 d V 1 ≤ d DV 1 .
To show the other inequality, let φ ∈ Iso ( Y ) \varphi\in\operatorname{Iso}(Y) φ ∈ Iso ( Y ) . We construct a partial matching R φ ∈ PM ( P , Q ) \mathcal{R}_\varphi\in\operatorname{PM}(\mathcal{P},\mathcal{Q}) R φ ∈ PM ( P , Q ) as follows:
(i) if L n ( { p = i } ) \mathcal{L}^n(\{p=i\}) L n ({ p = i }) and L n ( { ( φ ∘ q ) = i } ) \mathcal{L}^n(\{(\varphi\circ q)=i\}) L n ({( φ ∘ q ) = i }) are nonzero, append ( E i ′ , E φ − 1 ( i ) ′ ′ ) ∈ R φ (E'_i,E''_{\varphi^{-1}(i)})\in\mathcal{R}_\varphi ( E i ′ , E φ − 1 ( i ) ′′ ) ∈ R φ ;
(ii) if L n ( { p = i } ) \mathcal{L}^n(\{p=i\}) L n ({ p = i }) is nonzero and L n ( { ( φ ∘ q ) = i } ) = 0 \mathcal{L}^n(\{(\varphi\circ q)=i\})=0 L n ({( φ ∘ q ) = i }) = 0 , append ( E i ′ , ∗ ) ∈ R φ (E'_i,\ast)\in\mathcal{R}_\varphi ( E i ′ , ∗ ) ∈ R φ ;
(iii) append ( ∗ , E φ − 1 ( i ) ′ ′ ) ∈ R φ (\ast,E''_{\varphi^{-1}(i)})\in\mathcal{R}_\varphi ( ∗ , E φ − 1 ( i ) ′′ ) ∈ R φ if the opposite of (ii) is true.
Thus
d V 1 ( p , q ) = inf φ ∈ Iso ( Y ) ∫ Ω δ ( p , φ ∘ q ) d L n by Corollary 21 = 1 2 inf φ ∈ Iso ( Y ) ∑ i ∈ Y L n ( { p = i } △ { φ ∘ q = i } ) by Lemma 23 = 1 2 inf φ ∈ Iso ( Y ) ∑ ( E ′ , E ′ ′ ) ∈ R φ L n ( E ′ △ E ′ ′ ) ≥ d D V 1 ( P , Q ) . \begin{aligned}
d_V^1(p,q) &= \inf_{\varphi\in\operatorname{Iso}(Y)}\int_\Omega\delta(p,\varphi\circ q)\,d\mathcal{L}^n &&\text{by Corollary 21}\\
&= \frac{1}{2}\inf_{\varphi\in\operatorname{Iso}(Y)}\sum_{i\in Y}\mathcal{L}^n(\{p=i\}\mathbin{\triangle}\{\varphi\circ q=i\}) &&\text{by Lemma 23}\\
&= \frac{1}{2}\inf_{\varphi\in\operatorname{Iso}(Y)}\sum_{(E',E'')\in\mathcal{R}_\varphi}\mathcal{L}^n(E'\mathbin{\triangle}E'')\\
&\ge d_{\mathrm{DV}}^1(\mathcal{P},\mathcal{Q}).
\end{aligned} d V 1 ( p , q ) = φ ∈ Iso ( Y ) inf ∫ Ω δ ( p , φ ∘ q ) d L n = 2 1 φ ∈ Iso ( Y ) inf i ∈ Y ∑ L n ({ p = i } △ { φ ∘ q = i }) = 2 1 φ ∈ Iso ( Y ) inf ( E ′ , E ′′ ) ∈ R φ ∑ L n ( E ′ △ E ′′ ) ≥ d DV 1 ( P , Q ) . by Corollary 21 by Lemma 23
This concludes our proof that d V 1 = d D V 1 d_V^1=d_{\mathrm{DV}}^1 d V 1 = d DV 1 .
Proof that d V 2 = d D V 2 d_V^2=d_{\mathrm{DV}}^2 d V 2 = d DV 2 . Denote by C ( P ) \mathcal{C}(\mathcal{P}) C ( P ) and C ( p ) \mathcal{C}(p) C ( p ) the collections of coarsenings of a cell structure P \mathcal{P} P and a piecewise constant function p p p , respectively. Also, let S ( p ) \mathcal{S}(p) S ( p ) be the cell structure defined by the level sets of a piecewise constant function p p p . By the previous case,
d V 2 ( p , q ) = inf p ′ ∈ C ( p ) , q ′ ∈ C ( q ) d V 1 ( p ′ , q ′ ) = inf p ′ ∈ C ( p ) , q ′ ∈ C ( q ) d D V 1 ( S ( p ′ ) , S ( q ′ ) ) . d_V^2(p,q)=\inf_{p'\in\mathcal{C}(p),q'\in\mathcal{C}(q)}d_V^1(p',q')=\inf_{p'\in\mathcal{C}(p),q'\in\mathcal{C}(q)}d_{\mathrm{DV}}^1(\mathcal{S}(p'),\mathcal{S}(q')). d V 2 ( p , q ) = p ′ ∈ C ( p ) , q ′ ∈ C ( q ) inf d V 1 ( p ′ , q ′ ) = p ′ ∈ C ( p ) , q ′ ∈ C ( q ) inf d DV 1 ( S ( p ′ ) , S ( q ′ )) .
On the other, by definition,
d D V 2 ( P , Q ) = inf P ′ ∈ C ( P ) , Q ′ ∈ C ( Q ) d D V 1 ( P ′ , Q ′ ) . d_{\mathrm{DV}}^2(\mathcal{P},\mathcal{Q})=\inf_{\mathcal{P}'\in\mathcal{C}(\mathcal{P}),\mathcal{Q}'\in\mathcal{C}(\mathcal{Q})}d_{\mathrm{DV}}^1(\mathcal{P}',\mathcal{Q}'). d DV 2 ( P , Q ) = P ′ ∈ C ( P ) , Q ′ ∈ C ( Q ) inf d DV 1 ( P ′ , Q ′ ) .
Thus it suffices to show that if P ′ ∈ C ( P ) \mathcal{P}'\in\mathcal{C}(\mathcal{P}) P ′ ∈ C ( P ) then there exists a p ′ ∈ C ( p ) p'\in\mathcal{C}(p) p ′ ∈ C ( p ) such that S ( p ′ ) \mathcal{S}(p') S ( p ′ ) corresponds to P ′ \mathcal{P}' P ′ and vice versa. We begin with a coarsened cell structure P ′ \mathcal{P}' P ′ . Let p ∈ PC ( Ω ; Y ) p\in\operatorname{PC}(\Omega;Y) p ∈ PC ( Ω ; Y ) be the index map defined at the beginning of the proof. We construct a coarsening p ′ ∈ C ( p ) p'\in\mathcal{C}(p) p ′ ∈ C ( p ) as follows. Each cell F ∈ P ′ F \in\mathcal{P}' F ∈ P ′ is union of cells of P \mathcal{P} P : F ′ = ⨆ α ∈ A ( F ) E α ′ F' = \bigsqcup_{\alpha\in A(F)} E'_{\alpha} F ′ = ⨆ α ∈ A ( F ) E α ′ . Choose α ∈ A ( F ) \alpha\in A(F) α ∈ A ( F ) and set p ′ ( F ) = α p'(F) = \alpha p ′ ( F ) = α . Then p ′ p' p ′ is a coarsening of p p p whose level sets are the cells of P ′ \mathcal{P}' P ′ .
Conversely, let p ′ ∈ C ( p ) p' \in C(p) p ′ ∈ C ( p ) . By definition, the inverse image of its level set is the inverse image of a union of non-adjacent level-sets. As such, p ′ p' p ′ partitions the domain into
Ω = ⨆ α ∈ A Ω α p ′ \Omega= \bigsqcup_{\alpha\in A} \Omega^{p'}_{\alpha} Ω = α ∈ A ⨆ Ω α p ′
where Ω α p ′ = ( p ′ ) − 1 ( α ) = ⋃ i ∈ I p − 1 ( { α i } ) \Omega^{p'}_{\alpha} = (p')^{-1}(\alpha) = \bigcup_{i \in I} p^{-1}(\{\alpha_i\}) Ω α p ′ = ( p ′ ) − 1 ( α ) = ⋃ i ∈ I p − 1 ({ α i }) for some I ⊂ A I \subset A I ⊂ A . Since each cell Ω α p ′ \Omega^{p'}_{\alpha} Ω α p ′ is a union of non-adjacent cells of P \mathcal{P} P , it follows that S ( p ′ ) ∈ C ( P ) S(p') \in C(\mathcal{P}) S ( p ′ ) ∈ C ( P ) .
Proposition 24. Let Ω \Omega Ω be a open, connected, bounded subset of R n \mathbb{R}^{n} R n and let P \mathcal{P} P and Q \mathcal{Q} Q be cell structures of Ω \Omega Ω . The minima in Definitions 1 and Definition 4 are realized.
Proof. By Theorem 5 and Proposition 4 it suffices to show that the minima in Definition 4 are realized. We begin by considering d D V 1 d_{DV}^{1} d D V 1 . Suppose we partition Ω \Omega Ω into P = { E i } i ∈ A \mathcal{P} = \{E_i\}_{i \in A} P = { E i } i ∈ A and Q = { F j } j ∈ B \mathcal{Q} = \{F_j\}_{j \in B} Q = { F j } j ∈ B , where A A A and B B B are both countably infinite subsets of N \mathbb{N} N . The argument is similar when one of A A A or B B B is finite. Pick a minimizing sequence { R k } k ∈ N ⊂ PM ( P , Q ) \{\mathfrak{R}_k\}_{k \in\mathbb{N}} \subset\operatorname{PM}(\mathcal{P}, \mathcal{Q}) { R k } k ∈ N ⊂ PM ( P , Q ) of
L ( R ) : = ∑ ( E , F ) ∈ R L n ( E △ F ) L(\mathfrak{R}) := \sum_{(E,F) \in\mathfrak{R}} \mathcal{L}^{n}(E \mathbin{\triangle} F) L ( R ) := ( E , F ) ∈ R ∑ L n ( E △ F )
over all R ∈ PM ( P , Q ) \mathfrak{R} \in\operatorname{PM}(\mathcal{P}, \mathcal{Q}) R ∈ PM ( P , Q ) . Before we construct a candidate R ∗ ∈ PM ( P , Q ) \mathfrak{R}^{*} \in\operatorname{PM}(\mathcal{P}, \mathcal{Q}) R ∗ ∈ PM ( P , Q ) and show it obtains the infimum, we first note that for any R ∈ PM ( P , Q ) \mathfrak{R} \in\operatorname{PM}(\mathcal{P}, \mathcal{Q}) R ∈ PM ( P , Q ) ,
∣ L ( R ) − L N ( R ) ∣ ≤ ∑ i > N L n ( E i ) + ∑ j > N L n ( F j ) ⟶ 0 as N → ∞ . (34) \left|L(\mathfrak{R}) - L_{N}(\mathfrak{R})\right| \leq\sum_{i>N} \mathcal{L}^{n}(E_i) + \sum_{j>N} \mathcal{L}^{n}(F_j) \longrightarrow0 \quad\text{as } N \to\infty. \tag*{(34)} ∣ L ( R ) − L N ( R ) ∣ ≤ i > N ∑ L n ( E i ) + j > N ∑ L n ( F j ) ⟶ 0 as N → ∞. (34)
where
L N ( R ) : = ∑ ( E i , F j ) ∈ R i , j ≤ N L n ( E i △ F j ) + ∑ i ≤ N ∄ j ≤ N : ( E i , F j ) ∈ R L n ( E i ) + ∑ j ≤ N ∄ i ≤ N : ( E i , F j ) ∈ R L n ( F j ) . L_N(\mathfrak{R}) := \sum_{\substack{(E_i,F_j)\in\mathfrak{R}\\ i,j\leq N}} \mathcal{L}^{n}(E_i\mathbin{\triangle}F_j) + \sum_{\substack{i\leq N\\ \nexists j\leq N:(E_i,F_j)\in\mathfrak{R}}} \mathcal{L}^{n}(E_i) + \sum_{\substack{j\leq N\\ \nexists i\leq N:(E_i,F_j)\in\mathfrak{R}}} \mathcal{L}^{n}(F_j). L N ( R ) := ( E i , F j ) ∈ R i , j ≤ N ∑ L n ( E i △ F j ) + i ≤ N ∄ j ≤ N : ( E i , F j ) ∈ R ∑ L n ( E i ) + j ≤ N ∄ i ≤ N : ( E i , F j ) ∈ R ∑ L n ( F j ) .
For any ( i , j , k ) ∈ A × B × N (i,j,k) \in A \times B \times\mathbb{N} ( i , j , k ) ∈ A × B × N , we define
c i j k = { 1 if ( i , j ) ∈ R k , 0 otherwise c_{ijk} =
\begin{cases}
1 & \text{if } (i,j) \in\mathfrak{R}_k,\\
0 & \text{otherwise}
\end{cases} c ij k = { 1 0 if ( i , j ) ∈ R k , otherwise
to encode whether E i E_i E i and F j F_j F j were matched at step k k k of the minimizing sequence. Enumerate A × B A \times B A × B with { ( i m , j m ) } m = 1 ∞ \{(i_m,j_m)\}_{m=1}^{\infty} {( i m , j m ) } m = 1 ∞ . Since c i 1 j 1 k ∈ { 0 , 1 } c_{i_1j_1k} \in\{0,1\} c i 1 j 1 k ∈ { 0 , 1 } , we can pick an infinite subset N 1 N_1 N 1 of N \mathbb{N} N such that c i 1 j 1 k c_{i_1j_1k} c i 1 j 1 k is constant for k ∈ N 1 k \in N_1 k ∈ N 1 ; denote this constant by c 1 c_1 c 1 and pick any such k 1 ∈ N 1 k_1 \in N_1 k 1 ∈ N 1 . Similarly, there is an infinite subset N 2 N_2 N 2 of N 1 N_1 N 1 such that c 2 : = c i 2 j 2 k c_2 := c_{i_2j_2k} c 2 := c i 2 j 2 k is constant for k ∈ N 2 k \in N_2 k ∈ N 2 ; pick a k 2 ∈ N 2 k_2 \in N_2 k 2 ∈ N 2 such that k 2 > k 1 k_2 > k_1 k 2 > k 1 . We repeat this process for all m ∈ { 1 , 2 , … } m \in\{1,2,\ldots\} m ∈ { 1 , 2 , … } to obtain { c m } \{c_m\} { c m } and k 1 < k 2 < ⋯ k_1 < k_2 < \cdots k 1 < k 2 < ⋯ .
We define R ∗ \mathfrak{R}^{*} R ∗ with the following procedure. In the first step, we let R ∗ \mathfrak{R}^{*} R ∗ contain all the pairs ( i m , j m ) ∈ A × B (i_m,j_m) \in A \times B ( i m , j m ) ∈ A × B for which c m = 1 c_m = 1 c m = 1 . Then, if i ′ ∈ A i' \in A i ′ ∈ A is not present in the first entry of any of the pairs just added, we add ( i ′ , ∗ ) (i',*) ( i ′ , ∗ ) to R ∗ \mathfrak{R}^{*} R ∗ . Similarly, if j ′ ∈ B j' \in B j ′ ∈ B is not present in the second entry of any of the any pair added in the first step, we add ( ∗ , j ′ ) (*,j') ( ∗ , j ′ ) to R ∗ \mathfrak{R}^{*} R ∗ .
Let ε > 0 \varepsilon> 0 ε > 0 . By (34) we can choose N N N large enough so that
∣ L ( R ∗ ) − L ( R k m ) ∣ ≤ ∣ L ( R ∗ ) − L N ( R ∗ ) ∣ + ∣ L N ( R ∗ ) − L N ( R k m ) ∣ + ∣ L N ( R k m ) − L ( R k m ) ∣ ≤ ε + ∣ L N ( R ∗ ) − L N ( R k m ) ∣ . \begin{aligned}
\left| \mathcal{L}(\mathcal{R}^{*})-\mathcal{L}(\mathcal{R}_{k_m}) \right| \leq\left| \mathcal{L}(\mathcal{R}^{*})-\mathcal{L}_{N}(\mathcal{R}^{*}) \right|+\left| \mathcal{L}_{N}(\mathcal{R}^{*})-\mathcal{L}_{N}(\mathcal{R}_{k_m}) \right|+\left| \mathcal{L}_{N}(\mathcal{R}_{k_m})-\mathcal{L}(\mathcal{R}_{k_m}) \right| \\
&\leq\varepsilon+\left| \mathcal{L}_{N}(\mathcal{R}^{*})-\mathcal{L}_{N}(\mathcal{R}_{k_m}) \right|.
\end{aligned} ∣ L ( R ∗ ) − L ( R k m ) ∣ ≤ ∣ L ( R ∗ ) − L N ( R ∗ ) ∣ + ∣ L N ( R ∗ ) − L N ( R k m ) ∣ + ∣ L N ( R k m ) − L ( R k m ) ∣ ≤ ε + ∣ L N ( R ∗ ) − L N ( R k m ) ∣ .
Because the first summation used to define L N \mathcal{L}_{N} L N is a sum over (at most) N 2 N^{2} N 2 pairs in R \mathcal{R} R , for large enough m m m , the three families we sum over for L N ( R ∗ ) \mathcal{L}_{N}(\mathcal{R}^{*}) L N ( R ∗ ) are the same three families we use for L N ( R k m ) \mathcal{L}_{N}(\mathcal{R}_{k_m}) L N ( R k m ) . Letting ε → 0 \varepsilon\to0 ε → 0 concludes this portion of the proof.
We now consider the d D V 2 d^{2}_{\mathrm{DV}} d DV 2 . Pick a sequence of coarsenings { P k } k = 1 ∞ \{\mathcal{P}^{k}\}_{k=1}^{\infty} { P k } k = 1 ∞ of P \mathcal{P} P and coarsenings { Q k } k = 1 ∞ \{\mathcal{Q}^{k}\}_{k=1}^{\infty} { Q k } k = 1 ∞ of Q \mathcal{Q} Q so that
d D V 1 ( P k , Q k ) ⟶ d D V 2 ( P , Q ) as k → ∞ . d^{1}_{\mathrm{DV}}(\mathcal{P}^{k},\mathcal{Q}^{k}) \longrightarrow d^{2}_{\mathrm{DV}}(\mathcal{P},\mathcal{Q}) \quad\text{as } k\to\infty. d DV 1 ( P k , Q k ) ⟶ d DV 2 ( P , Q ) as k → ∞.
We will show that there exist “limit” coarsenings of { P k } \{\mathcal{P}^{k}\} { P k } and { Q k } \{\mathcal{Q}^{k}\} { Q k } denoted by P ∞ \mathcal{P}^{\infty} P ∞ and Q ∞ \mathcal{Q}^{\infty} Q ∞ , respectively, which satisfy
d D V 1 ( P ∞ , Q ∞ ) = d D V 2 ( P , Q ) . d^{1}_{\mathrm{DV}}(\mathcal{P}^{\infty},\mathcal{Q}^{\infty})=d^{2}_{\mathrm{DV}}(\mathcal{P},\mathcal{Q}). d DV 1 ( P ∞ , Q ∞ ) = d DV 2 ( P , Q ) .
We first define P ∞ \mathcal{P}^{\infty} P ∞ . Any coarsening P k \mathcal{P}^{k} P k defines an equivalence relation ∼ k \sim_{k} ∼ k on A A A , where i ∼ k j i\sim_{k}j i ∼ k j if there is a cell E ∈ P k E\in\mathcal{P}^{k} E ∈ P k so that ( E i ∪ E j ) ⊂ E (E_{i}\cup E_{j})\subset E ( E i ∪ E j ) ⊂ E . For any ( i , j , k ) ∈ A × A × N (i,j,k)\in A\times A\times\mathbb{N} ( i , j , k ) ∈ A × A × N , we define
c i j k P : = { 1 if i ∼ k j 0 otherwise . c^{\mathcal{P}}_{ijk}:=
\begin{cases}
1 & \text{if } i\sim_{k}j\\
0 & \text{otherwise}.
\end{cases} c ij k P := { 1 0 if i ∼ k j otherwise .
Enumerating A × A A\times A A × A with { ( i m , j m ) } \{(i_m,j_m)\} {( i m , j m )} we use a similar diagonalization argument as in the case of d D V 1 d^{1}_{\mathrm{DV}} d DV 1 to obtain a sequence { k m } \{k_m\} { k m } such that c m P : = c i m j m k l P c^{\mathcal{P}}_{m}:=c^{\mathcal{P}}_{i_mj_mk_l} c m P := c i m j m k l P is a constant function of l ≥ m l\geq m l ≥ m . This allows us to define the equivalence relation ∼ \sim ∼ where i m ∼ j m i_m\sim j_m i m ∼ j m if c m P = 1 c^{\mathcal{P}}_{m}=1 c m P = 1 , and hence, the coarsening
P ∞ : = { E [ i ] : = ⋃ j ∈ [ i ] E j : [ i ] ∈ A / ∼ } \mathcal{P}^{\infty}:=\left\{E_{[i]}:=\bigcup_{j\in[i]}E_j:[i]\in A/{\sim}\right\} P ∞ := ⎩ ⎨ ⎧ E [ i ] := j ∈ [ i ] ⋃ E j : [ i ] ∈ A / ∼ ⎭ ⎬ ⎫
of P \mathcal{P} P . Apply the same diagonal argument for Q \mathcal{Q} Q along the subsequence already selected for P \mathcal{P} P . Notice that adjacent cells in P \mathcal{P} P (and P ∞ \mathcal{P}^{\infty} P ∞ ) cannot belong to the same limiting class, otherwise, they would belong to the same class at a sufficiently large k k k , which is a contradiction. By subadditivity and lower semicontinuity of perimeter P \mathcal{P} P , P ∞ \mathcal{P}^{\infty} P ∞ and Q ∞ \mathcal{Q}^{\infty} Q ∞ are Caccioppoli partitions of Ω \Omega Ω .
Now consider the first N N N cells { E 1 , … , E N } \{E_{1},\ldots,E_{N}\} { E 1 , … , E N } of P \mathcal{P} P . Because for all sufficiently large k ∈ { k m } k\in\{k_m\} k ∈ { k m } , we have that i ∼ k j i\sim_{k}j i ∼ k j if and only if i ∼ j i\sim j i ∼ j (for i , j ∈ { 1 , … , N } i,j\in\{1,\ldots,N\} i , j ∈ { 1 , … , N } ), we have a cost zero matching between
P ∣ 1 , … , N k : = { E [ i ] : [ i ] ∈ { 1 , … , N } / ∼ k } \mathcal{P}^{k}_{|1,\ldots,N}:=\left\{E_{[i]}:[i]\in\{1,\ldots,N\}/{\sim_{k}}\right\} P ∣1 , … , N k := { E [ i ] : [ i ] ∈ { 1 , … , N } / ∼ k }
and P ∣ 1 , … , N ∞ \mathcal{P}^{\infty}_{|1,\ldots,N} P ∣1 , … , N ∞ (similarly defined). For such k k k , we get
d D V 1 ( P k , P ∞ ) ≤ 2 ∑ i > N L n ( E i ) ⟶ 0 as N → ∞ . d^{1}_{\mathrm{DV}}(\mathcal{P}^{k},\mathcal{P}^{\infty})\leq2\sum_{i>N}\mathcal{L}^{n}(E_i)\longrightarrow0 \quad\text{as } N\to\infty. d DV 1 ( P k , P ∞ ) ≤ 2 i > N ∑ L n ( E i ) ⟶ 0 as N → ∞.
A similar argument also gives us d D V 1 ( Q k , Q ∞ ) ⟶ 0 d^{1}_{\mathrm{DV}}(\mathcal{Q}^{k},\mathcal{Q}^{\infty})\longrightarrow0 d DV 1 ( Q k , Q ∞ ) ⟶ 0 as N → ∞ N\to\infty N → ∞ . Because d D V 1 d^{1}_{\mathrm{DV}} d DV 1 satisfies the triangle inequality,
d D V 1 ( P ∞ , Q ∞ ) ≤ d D V 1 ( P ∞ , P k ) + d D V 1 ( P k , Q k ) + d D V 1 ( Q k , Q ∞ ) . d^{1}_{\mathrm{DV}}(\mathcal{P}^{\infty},\mathcal{Q}^{\infty})\leq d^{1}_{\mathrm{DV}}(\mathcal{P}^{\infty},\mathcal{P}^{k})+d^{1}_{\mathrm{DV}}(\mathcal{P}^{k},\mathcal{Q}^{k})+d^{1}_{\mathrm{DV}}(\mathcal{Q}^{k},\mathcal{Q}^{\infty}). d DV 1 ( P ∞ , Q ∞ ) ≤ d DV 1 ( P ∞ , P k ) + d DV 1 ( P k , Q k ) + d DV 1 ( Q k , Q ∞ ) .
Recalling that lim k → ∞ d D V 1 ( P k , Q k ) = d D V 2 ( P , Q ) \lim_{k\to\infty}d^{1}_{\mathrm{DV}}(\mathcal{P}^{k},\mathcal{Q}^{k})=d^{2}_{\mathrm{DV}}(\mathcal{P},\mathcal{Q}) lim k → ∞ d DV 1 ( P k , Q k ) = d DV 2 ( P , Q ) , letting k → ∞ k\to\infty k → ∞ in the inequality above gives us that
d D V 1 ( P ∞ , Q ∞ ) ≤ d D V 2 ( P , Q ) . d^{1}_{\mathrm{DV}}(\mathcal{P}^{\infty},\mathcal{Q}^{\infty})\leq d^{2}_{\mathrm{DV}}(\mathcal{P},\mathcal{Q}). d DV 1 ( P ∞ , Q ∞ ) ≤ d DV 2 ( P , Q ) .
Now, since P ∞ \mathcal{P}^{\infty} P ∞ and Q ∞ \mathcal{Q}^{\infty} Q ∞ are coarsenings of P \mathcal{P} P and Q \mathcal{Q} Q , by definition, d D V ( P , Q ) ≤ d D V ( P ∞ , Q ∞ ) d_{\mathrm{DV}}(\mathcal{P},\mathcal{Q}) \le d_{\mathrm{DV}}(\mathcal{P}^{\infty},\mathcal{Q}^{\infty}) d DV ( P , Q ) ≤ d DV ( P ∞ , Q ∞ ) . By our previous result for the existence result for d D V d_{\mathrm{DV}} d DV , there exists an optimal partial matching between P ∞ \mathcal{P}^{\infty} P ∞ and Q ∞ \mathcal{Q}^{\infty} Q ∞ . This concludes the proof. □
Metric Properties
Recall that if d d d is non-negative, symmetric, and satisfies d ( M , M ) = 0 d(M,M)=0 d ( M , M ) = 0 for all M M M then it is called a dissimilarity.
Proposition 25. d V 1 d_{\mathrm{V}}^{1} d V 1 is a metric and d V 2 d_{\mathrm{V}}^{2} d V 2 is a dissimilarity but does not satisfy the triangle inequality.
Proof. Let M \mathcal{M} M and N \mathcal{N} N be cell structures and j ∈ { 1 , 2 } j \in\{1,2\} j ∈ { 1 , 2 } . It is obvious from either the discrete or continuous definitions that
d V j ( M , N ) = d V j ( N , M ) ≥ 0. d_{\mathrm{V}}^{j}(\mathcal{M},\mathcal{N}) = d_{\mathrm{V}}^{j}(\mathcal{N},\mathcal{M}) \ge0. d V j ( M , N ) = d V j ( N , M ) ≥ 0.
If d V 1 ( M , N ) = 0 d_{\mathrm{V}}^{1}(M,N)=0 d V 1 ( M , N ) = 0 then the symmetric difference of every pair of cells in an optimal matching has zero volume. That is, M M M and N N N differ up to a rearrangement of a set of measure zero and are equal as partitions of Ω \Omega Ω .
To show that d D V 1 d_{\mathrm{DV}}^{1} d DV 1 satisfies the triangle inequality let M = { M i } i ∈ I \mathcal{M}=\{M_i\}_{i\in I} M = { M i } i ∈ I , N = { N j } j ∈ J \mathcal{N}=\{N_j\}_{j\in J} N = { N j } j ∈ J , and O = { O k } k ∈ K \mathcal{O}=\{O_k\}_{k\in K} O = { O k } k ∈ K be cell structures in Ω \Omega Ω and let R R R and S S S be optimal partial matchings between the cells of M \mathcal{M} M and N \mathcal{N} N and those of N \mathcal{N} N and O \mathcal{O} O , respectively. Define
T ^ ⊂ ( I ∪ { ∗ } ) × ( J ∪ { ∗ } ) × ( K ∪ { ∗ } ) \widehat{T} \subset(I \cup\{\ast\}) \times(J \cup\{\ast\}) \times(K \cup\{\ast\}) T ⊂ ( I ∪ { ∗ }) × ( J ∪ { ∗ }) × ( K ∪ { ∗ })
to be the set of triplets of the following three types
( i , j , k ) (i,j,k) ( i , j , k ) if ( M i , N j ) ∈ R (M_i,N_j)\in R ( M i , N j ) ∈ R , ( N j , O k ) ∈ S (N_j,O_k)\in S ( N j , O k ) ∈ S , N j ≠ ∗ N_j \ne\ast N j = ∗ , and ( M i , O k ) ≠ ( ∗ , ∗ ) (M_i,O_k)\ne(\ast,\ast) ( M i , O k ) = ( ∗ , ∗ ) ,
( i , ∗ , ∗ ) (i,\ast,\ast) ( i , ∗ , ∗ ) if ( M i , ∗ ) ∈ R (M_i,\ast)\in R ( M i , ∗ ) ∈ R ,
and ( ∗ , ∗ , k ) (\ast,\ast,k) ( ∗ , ∗ , k ) if ( ∗ , N k ) ∈ S (\ast,N_k)\in S ( ∗ , N k ) ∈ S .
As
T = { ( M i , O k ) : ∃ j s.t. ( i , j , k ) ∈ T ^ } T = \left\{(M_i,O_k): \exists j\ \text{s.t. } (i,j,k)\in\widehat{T}\right\} T = { ( M i , O k ) : ∃ j s.t. ( i , j , k ) ∈ T }
is a partial matching between M M M and O O O , it follows that
d D V 1 ( M , O ) ≤ 1 2 ∑ ( i , j , k ) ∈ T ^ ∣ M i △ O k ∣ ≤ 1 2 ∑ ( i , j , k ) ∈ T ^ ( ∣ M i △ N j ∣ + ∣ N j △ O k ∣ ) = 1 2 ∑ ( i , j ) ∈ R j ≠ J ^ ∣ M i △ N j ∣ + 1 2 ∑ ( j , k ) ∈ S j ≠ J ^ ∣ N j △ O k ∣ ≤ d D V 1 ( M , N ) + d D V 1 ( N , O ) , d_{\mathrm{DV}}^{1}(M,O) \le\frac{1}{2}\sum_{(i,j,k)\in\widehat{T}} |M_i\mathbin{\triangle}O_k|
\le\frac{1}{2}\sum_{(i,j,k)\in\widehat{T}} \left(|M_i\mathbin{\triangle}N_j|+|N_j\mathbin{\triangle}O_k|\right)
= \frac{1}{2}\sum_{\substack{(i,j)\in R\\j\ne\widehat{J}}}|M_i\mathbin{\triangle}N_j|+\frac{1}{2}\sum_{\substack{(j,k)\in S\\j\ne\widehat{J}}}|N_j\mathbin{\triangle}O_k|
\le d_{\mathrm{DV}}^{1}(M,N)+d_{\mathrm{DV}}^{1}(N,O), d DV 1 ( M , O ) ≤ 2 1 ( i , j , k ) ∈ T ∑ ∣ M i △ O k ∣ ≤ 2 1 ( i , j , k ) ∈ T ∑ ( ∣ M i △ N j ∣ + ∣ N j △ O k ∣ ) = 2 1 ( i , j ) ∈ R j = J ∑ ∣ M i △ N j ∣ + 2 1 ( j , k ) ∈ S j = J ∑ ∣ N j △ O k ∣ ≤ d DV 1 ( M , N ) + d DV 1 ( N , O ) ,
where J ^ = { j : ( ∗ , j ) ∈ R , ( j , ∗ ) ∈ S } \widehat{J}=\{j:(\ast,j)\in R,(j,\ast)\in S\} J = { j : ( ∗ , j ) ∈ R , ( j , ∗ ) ∈ S } .
Failure of triangle inequality for d V 2 d_{\mathrm{V}}^{2} d V 2 . Let Ω = D 2 \Omega=\mathbb{D}^{2} Ω = D 2 be the open disk of area one in two dimensions. Consider the following three cell structures. Let A = { g 1 , g 2 , g 3 } A=\{g_1,g_2,g_3\} A = { g 1 , g 2 , g 3 } be a partition of the disk into equal thirds, B = { g 4 , g 5 , g 6 , g 7 } B=\{g_4,g_5,g_6,g_7\} B = { g 4 , g 5 , g 6 , g 7 } be similar to A A A with an inclusion g 7 g_7 g 7 such that g 4 , g 5 , g 6 g_4,g_5,g_6 g 4 , g 5 , g 6 are nonadjacent and 0 < ∣ g 7 ∣ < 1 3 0<|g_7|<\frac{1}{3} 0 < ∣ g 7 ∣ < 3 1 , and C = { g 8 } C=\{g_8\} C = { g 8 } . A visualization of the cell structures can be found in Figure 6 . Since every cell in A A A is adjacent to one another, d V 2 ( A , C ) = 2 / 3 d_{\mathrm{V}}^{2}(A,C)=2/3 d V 2 ( A , C ) = 2/3 . However, both d V 2 ( A , B ) = ∣ g 7 ∣ d_{\mathrm{V}}^{2}(A,B)=|g_7| d V 2 ( A , B ) = ∣ g 7 ∣ and d V 2 ( B , C ) d_{\mathrm{V}}^{2}(B,C) d V 2 ( B , C ) since { g 4 , g 5 , g 6 } ↦ { g 8 } \{g_4,g_5,g_6\}\mapsto\{g_8\} { g 4 , g 5 , g 6 } ↦ { g 8 } . By construction d V 2 ( A , C ) ≠ d V 2 ( A , B ) + d V 2 ( B , C ) d_{\mathrm{V}}^{2}(A,C)\ne d_{\mathrm{V}}^{2}(A,B)+d_{\mathrm{V}}^{2}(B,C) d V 2 ( A , C ) = d V 2 ( A , B ) + d V 2 ( B , C ) .
Figure 6. Failure of the triangle inequality for d V 2 d_{\mathrm{V}}^{2} d V 2 .
A notion relevant to our computational experiments of § 6 is that of a conditionally negative definite metric. A symmetric function ψ : Z × Z → R \psi:\mathbb{Z}\times\mathbb{Z}\to\mathbb{R} ψ : Z × Z → R is called conditionally negative definite if for any finite subset { z 1 , … , z m } \{z_1,\ldots,z_m\} { z 1 , … , z m } of Z \mathbb{Z} Z , the matrix D = ( ψ ( z i , z j ) ) i , j = 1 , … , m D=(\psi(z_i,z_j))_{i,j=1,\ldots,m} D = ( ψ ( z i , z j ) ) i , j = 1 , … , m is conditionally negative definite, i.e., for any vector α T = ( α 1 , … , α m ) ∈ R m \alpha^T=(\alpha_1,\ldots,\alpha_m)\in\mathbb{R}^m α T = ( α 1 , … , α m ) ∈ R m such that ∑ α i = 0 \sum\alpha_i=0 ∑ α i = 0 , we have that α T D α ≤ 0 \alpha^T D\alpha\le0 α T D α ≤ 0 . The next proposition shows that even for cellular structures within intervals of R \mathbb{R} R , the volume exchange metric is not conditionally negative definite.
Proposition 26. If Ω \Omega Ω is an open interval in R \mathbb{R} R , then d V 1 d_{\mathrm{V}}^{1} d V 1 is not conditionally negative definite.
Proof. The distance matrix
D = ( d V 1 ( A i , A j ) ) i , j = 1 , … , 5 = ( 0 2 2 1 1 2 0 2 1 1 2 2 0 1 1 1 1 1 0 2 1 1 1 2 0 ) D=\left(d^{1}_{V}(A_i,A_j)\right)_{i,j=1,\ldots,5}=
\begin{pmatrix}
0 & 2 & 2 & 1 & 1\\
2 & 0 & 2 & 1 & 1\\
2 & 2 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 2\\
1 & 1 & 1 & 2 & 0
\end{pmatrix} D = ( d V 1 ( A i , A j ) ) i , j = 1 , … , 5 = 0 2 2 1 1 2 0 2 1 1 2 2 0 1 1 1 1 1 0 2 1 1 1 2 0
for the five cell-structures A 1 , … , A 5 A_1,\ldots,A_5 A 1 , … , A 5 of Ω = ( 0 , 4 ) ⊂ R \Omega=(0,4)\subset\mathbb{R} Ω = ( 0 , 4 ) ⊂ R depicted in Figure 7 is not conditionally negative definite. Indeed, for the vector α T = ( 2 , 2 , 2 , − 3 , − 3 ) \alpha^T=(2,2,2,-3,-3) α T = ( 2 , 2 , 2 , − 3 , − 3 ) we get α T D α = 12 \alpha^T D\alpha=12 α T D α = 12 . □
Figure 7. Five cell structures on the interval (0, 4).
A similar example can be constructed when Ω \Omega Ω is the open unit cube in R n \mathbb{R}^n R n . One simply needs to take the cells of each of the five partitions of the open interval in the proof of the previous proposition and take its Cartesian product with ( 0 , 1 ) n − 1 (0,1)^{n-1} ( 0 , 1 ) n − 1 .
The following theorem states that the discrete one-to-one volume exchange metric is equal to an equivalent dual formulation:
d D V 1 ∗ ( P , Q ) : = L n ( Ω ) − max R ∈ P M ( P , Q ) ∑ ( E , F ) ∈ R L n ( E ∩ F ) . (35) d^{1*}_{DV}(\mathcal{P},\mathcal{Q}):=\mathcal{L}^n(\Omega)-\max_{\mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q})}\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\cap F). \tag*{(35)} d D V 1 ∗ ( P , Q ) := L n ( Ω ) − R ∈ PM ( P , Q ) max ( E , F ) ∈ R ∑ L n ( E ∩ F ) . (35)
Theorem 27. Suppose P \mathcal{P} P and Q \mathcal{Q} Q are cell structures of a common bounded, open, connected domain Ω ⊂ R n \Omega\subset\mathbb{R}^n Ω ⊂ R n . Then
d D V 1 ( P , Q ) = d D V 1 ∗ ( P , Q ) . d^{1}_{DV}(\mathcal{P},\mathcal{Q})=d^{1*}_{DV}(\mathcal{P},\mathcal{Q}). d D V 1 ( P , Q ) = d D V 1 ∗ ( P , Q ) .
Proof. By the definition of a partial matching R ∈ P M ( P , Q ) \mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) ,
∑ ( E , F ) ∈ R L n ( E ) = ∑ E ∈ P L n ( E ) = L n ( Ω ) = ∑ F ∈ Q L n ( F ) = ∑ ( E , F ) ∈ R L n ( F ) . \sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E)=\sum_{E\in\mathcal{P}}\mathcal{L}^n(E)=\mathcal{L}^n(\Omega)=\sum_{F\in\mathcal{Q}}\mathcal{L}^n(F)=\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(F). ( E , F ) ∈ R ∑ L n ( E ) = E ∈ P ∑ L n ( E ) = L n ( Ω ) = F ∈ Q ∑ L n ( F ) = ( E , F ) ∈ R ∑ L n ( F ) .
Thus, for any partial matching R ∈ P M ( P , Q ) \mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) ,
L n ( Ω ) − ∑ ( E , F ) ∈ R L n ( E ∩ F ) = ∑ ( E , F ) ∈ R 1 2 ( L n ( E ) + L n ( F ) ) − L n ( E ∩ F ) = 1 2 ∑ ( E , F ) ∈ R ( L n ( E ) − L n ( E ∩ F ) + L n ( F ) − L n ( E ∩ F ) ) = 1 2 ∑ ( E , F ) ∈ R L n ( E △ F ) . \begin{aligned}
\mathcal{L}^n(\Omega)-\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\cap F)
=\sum_{(E,F)\in\mathfrak{R}}\frac{1}{2}\left(\mathcal{L}^n(E)+\mathcal{L}^n(F)\right)-\mathcal{L}^n(E\cap F) \\
&=\frac{1}{2}\sum_{(E,F)\in\mathfrak{R}}\left(\mathcal{L}^n(E)-\mathcal{L}^n(E\cap F)+\mathcal{L}^n(F)-\mathcal{L}^n(E\cap F)\right) \\
&=\frac{1}{2}\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\triangle F).
\end{aligned} L n ( Ω ) − ( E , F ) ∈ R ∑ L n ( E ∩ F ) = ( E , F ) ∈ R ∑ 2 1 ( L n ( E ) + L n ( F ) ) − L n ( E ∩ F ) = 2 1 ( E , F ) ∈ R ∑ ( L n ( E ) − L n ( E ∩ F ) + L n ( F ) − L n ( E ∩ F ) ) = 2 1 ( E , F ) ∈ R ∑ L n ( E △ F ) .
Because d D V 1 ∗ d^{1*}_{DV} d D V 1 ∗ can be formulated as a minimization problem, i.e.,
L n ( Ω ) − max R ∈ P M ( E , F ) ∑ ( E , F ) ∈ R L n ( E ∩ F ) = min R ∈ P M ( P , Q ) { L n ( Ω ) − ∑ ( E , F ) ∈ R L n ( E ∩ F ) } , \mathcal{L}^n(\Omega)-\max_{\mathfrak{R}\in\mathrm{PM}(E,F)}\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\cap F)
=\min_{\mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q})}\left\{\mathcal{L}^n(\Omega)-\sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\cap F)\right\}, L n ( Ω ) − R ∈ PM ( E , F ) max ( E , F ) ∈ R ∑ L n ( E ∩ F ) = R ∈ PM ( P , Q ) min ⎩ ⎨ ⎧ L n ( Ω ) − ( E , F ) ∈ R ∑ L n ( E ∩ F ) ⎭ ⎬ ⎫ ,
we get that d D V 1 ∗ ( P , Q ) = d D V 1 ( P , Q ) d^{1*}_{DV}(\mathcal{P},\mathcal{Q})=d^{1}_{DV}(\mathcal{P},\mathcal{Q}) d D V 1 ∗ ( P , Q ) = d D V 1 ( P , Q ) . □
We note that the proof of Theorem 27 also says that R o p t \mathfrak{R}^{\mathrm{opt}} R opt maximizes ∑ ( E , F ) ∈ R L n ( E ∩ F ) \sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\cap F) ∑ ( E , F ) ∈ R L n ( E ∩ F ) over all R ∈ P M ( P , Q ) \mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) if and only if it minimizes ∑ ( E , F ) ∈ R L n ( E △ F ) \sum_{(E,F)\in\mathfrak{R}}\mathcal{L}^n(E\triangle F) ∑ ( E , F ) ∈ R L n ( E △ F ) over all R ∈ P M ( P , Q ) \mathfrak{R}\in\mathrm{PM}(\mathcal{P},\mathcal{Q}) R ∈ PM ( P , Q ) .
Computing d D V 1 d_{\mathrm{DV}}^{1} d DV 1
In the remainder of the paper, we assume that the cell structures have a finite number of cells. We outline a procedure to find the partial matching R o p t ∈ PM ( I , J ) R^{\mathrm{opt}} \in\operatorname{PM}(I,J) R opt ∈ PM ( I , J ) that minimizes the volume exchange using the formulation in Equation (35) . Towards that end, we construct a weighted balanced bipartite graph B = ( U , V , E ) B=(U,V,E) B = ( U , V , E ) which encapsulates the set of admissible partial matchings. Let U 1 U_{1} U 1 include a vertex u i u_{i} u i for each cell U i ∈ M U_{i} \in M U i ∈ M , and let U 2 U_{2} U 2 be a collection of “dummy” vertices u j ∗ u_{j}^{*} u j ∗ for each cell V j V_{j} V j of N N N . Set U = U 1 ∪ U 2 U=U_{1}\cup U_{2} U = U 1 ∪ U 2 , and define V V V , V 1 V_{1} V 1 , and V 2 V_{2} V 2 analogously so that ∣ U ∣ = ∣ V ∣ |U|=|V| ∣ U ∣ = ∣ V ∣ .
E E E consists of edges of three types:
an edge e i ∗ e_{i}^{*} e i ∗ with weight w i ∗ = 0 w_{i}^{*}=0 w i ∗ = 0 between each vertex u i ∈ U 1 u_{i}\in U_{1} u i ∈ U 1 and the corresponding dummy vertex v i ∗ ∈ V 2 v_{i}^{*}\in V_{2} v i ∗ ∈ V 2 ;
an edge e j ∗ e_{j}^{*} e j ∗ with weight w ^ j ∗ = 0 \hat{w}_{j}^{*}=0 w ^ j ∗ = 0 between each vertex v j ∈ V 1 v_{j}\in V_{1} v j ∈ V 1 and the corresponding dummy vertex u j ∗ ∈ U 2 u_{j}^{*}\in U_{2} u j ∗ ∈ U 2 ;
an edge e i j e_{ij} e ij is included between vertices u i ∈ U 1 u_{i}\in U_{1} u i ∈ U 1 and v j ∈ V 1 v_{j}\in V_{1} v j ∈ V 1 when their corresponding cells overlap, with weight w i j = ∣ U i ∩ V j ∣ w_{ij}=|U_{i}\cap V_{j}| w ij = ∣ U i ∩ V j ∣ .
Then
d D V 1 ( M , N ) = ∣ Ω ∣ − max x ∑ i , j = 1 ∣ U ∣ Adj ( B ) i j x i j d_{\mathrm{DV}}^{1}(M,N)=|\Omega|-\max_{\mathbf{x}\ } \sum_{i,j=1}^{|U|}\operatorname{Adj}(B)_{ij}x_{ij} d DV 1 ( M , N ) = ∣Ω∣ − x max i , j = 1 ∑ ∣ U ∣ Adj ( B ) ij x ij
where Adj ( B ) \operatorname{Adj}(B) Adj ( B ) is the weighted adjacency matrix of B B B (where non-edges have weight zero) and x i j \mathbf{x}_{ij} x ij is a binary decision variable with the constraint ∑ j = 1 ∣ U ∣ x i j = 1 \sum_{j=1}^{|U|}x_{ij}=1 ∑ j = 1 ∣ U ∣ x ij = 1 for all 1 ≤ i ≤ ∣ U ∣ 1\leq i\leq|U| 1 ≤ i ≤ ∣ U ∣ , similarly for j j j . The right hand side is a linear assignment problem that can be solved using classical methods such as the Hungarian algorithm or the Jonker–Volgenant–Castanon algorithm [17–19], which have time complexity O ( max { ∣ I ∣ , ∣ J ∣ } 3 ) O(\max\{|I|,|J|\}^{3}) O ( max { ∣ I ∣ , ∣ J ∣ } 3 ) .
Computing d D V 2 d_{\mathrm{DV}}^{2} d DV 2
We derive the set of independent matching between a pair of cellular structures from the adjacency graph on their cells. The collection of independent matching between cellular structures M M M and N N N is in general much larger than the class of partial matchings between them. In particular, the matching realizing d D V 2 ( M , N ) d_{\mathrm{DV}}^{2}(M,N) d DV 2 ( M , N ) minimizes the symmetric difference between subcollections of non-adjacent cells; the previous metric only permits matchings between individual cells. We outline a procedure to find that optimal matching R o p t ∈ IM ( I , J ) R^{\mathrm{opt}}\in\operatorname{IM}(I,J) R opt ∈ IM ( I , J ) .
Suppose σ ⊂ I \sigma\subset I σ ⊂ I and let M σ M^{\sigma} M σ denote a subcollection of cells indexed by σ \sigma σ . Let x ∈ { 0 , 1 } ∣ I ∣ \mathbf{x}\in\{0,1\}^{|I|} x ∈ { 0 , 1 } ∣ I ∣ be a binary integer vector. We say that x σ \mathbf{x}^{\sigma} x σ corresponds to M σ M^{\sigma} M σ if x i σ = χ U i ∈ M σ x_{i}^{\sigma}=\chi_{U_{i}\in M^{\sigma}} x i σ = χ U i ∈ M σ . Suppose x σ \mathbf{x}^{\sigma} x σ and y τ \mathbf{y}^{\tau} y τ correspond to subcollections M σ M^{\sigma} M σ and N τ N^{\tau} N τ and let Z σ τ ∈ R ∣ I ∣ × ∣ J ∣ Z^{\sigma\tau}\in\mathbb{R}^{|I|\times|J|} Z σ τ ∈ R ∣ I ∣ × ∣ J ∣ denote their outer product. Consider the real vectors α ∈ R ∣ I ∣ \alpha\in\mathbb{R}^{|I|} α ∈ R ∣ I ∣ and β ∈ R ∣ J ∣ \beta\in\mathbb{R}^{|J|} β ∈ R ∣ J ∣ such that α i = ∣ U i ∣ \alpha_{i}=|U_{i}| α i = ∣ U i ∣ and β j = ∣ V j ∣ \beta_{j}=|V_{j}| β j = ∣ V j ∣ and let Γ ∈ R ∣ I ∣ × ∣ J ∣ \Gamma\in\mathbb{R}^{|I|\times|J|} Γ ∈ R ∣ I ∣ × ∣ J ∣ be a real matrix such that Γ i j = ∣ U i ∩ V j ∣ \Gamma_{ij}=|U_{i}\cap V_{j}| Γ ij = ∣ U i ∩ V j ∣ . By construction ∣ M σ ∣ = α T x σ |M^{\sigma}|=\alpha^{\mathsf{T}}\mathbf{x}^{\sigma} ∣ M σ ∣ = α T x σ , ∣ N τ ∣ = β T y τ |N^{\tau}|=\beta^{\mathsf{T}}\mathbf{y}^{\tau} ∣ N τ ∣ = β T y τ , and
tr ( Γ T Z σ τ ) = ∑ U i ∈ M σ V j ∈ N τ ∣ U i ∩ V j ∣ . \operatorname{tr}\left(\Gamma^{\mathsf{T}}Z^{\sigma\tau}\right)=\sum_{\substack{U_{i}\in M^{\sigma}\\V_{j}\in N^{\tau}}}|U_{i}\cap V_{j}|. tr ( Γ T Z σ τ ) = U i ∈ M σ V j ∈ N τ ∑ ∣ U i ∩ V j ∣.
As such, if M σ M^{\sigma} M σ and N τ N^{\tau} N τ are subcollections paired by an independent matching R R R , then their symmetric difference equals
∣ M σ △ N τ ∣ = α T x σ + β T y τ − 2 tr ( Γ T Z σ τ ) |M^{\sigma}\triangle N^{\tau}|=\alpha^{\mathsf{T}}\mathbf{x}^{\sigma}+\beta^{\mathsf{T}}\mathbf{y}^{\tau}-2\operatorname{tr}\left(\Gamma^{\mathsf{T}}Z^{\sigma\tau}\right) ∣ M σ △ N τ ∣ = α T x σ + β T y τ − 2 tr ( Γ T Z σ τ )
and
d D V 2 ( M , N ) = 1 2 min R ∈ I M ( M , N ) ( ∑ ( σ , τ ) ∈ R α T x σ + β T y τ − 2 tr ( Γ T Z σ τ ) ) . (36) d_{\mathrm{DV}}^{2}(M,N)=\frac{1}{2}\min_{R\in\mathcal{I}\mathcal{M}(M,N)}\left(\sum_{(\sigma,\tau)\in R}\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{x}^{\sigma}+\boldsymbol{\beta}^{\mathsf{T}}\mathbf{y}^{\tau}-2\operatorname{tr}\left(\boldsymbol{\Gamma}^{\mathsf{T}}Z^{\sigma\tau}\right)\right). \tag*{(36)} d DV 2 ( M , N ) = 2 1 R ∈ I M ( M , N ) min ( σ , τ ) ∈ R ∑ α T x σ + β T y τ − 2 tr ( Γ T Z σ τ ) . (36)
R o p t R^{\mathrm{opt}} R opt can be determined by finding the optimal minimizing decision vectors x ∈ { 0 , 1 } ∣ I ∣ \mathbf{x}\in\{0,1\}^{|I|} x ∈ { 0 , 1 } ∣ I ∣ and y ∈ { 0 , 1 } ∣ J ∣ \mathbf{y}\in\{0,1\}^{|J|} y ∈ { 0 , 1 } ∣ J ∣ subject to the constraint that the corresponding subcollections consist of nonadjacent cells. In its current form, the many-to-many volume exchange dissimilarity is presented as a binary integer quadratic program, and the general class of binary integer quadratic programs is NP–complete. To reduce the burden of computing d D V 2 d_{\mathrm{DV}}^{2} d DV 2 a branch–cut algorithm is used to prune the search space. This is achieved by (1) approximating the solution using a faster quadratic program and (2) tightening the bounds to be integer valued using a branch-and-bound and cutting planes algorithm. Additional details regarding the branch–cut algorithm and its implementation can be found in [20].
In the next section, we only compute d D V 2 d_{\mathrm{DV}}^{2} d DV 2 for small sample windows taken from a larger cell structure. These windows typically contain ∼ 50 \sim50 ∼ 50 cells or less, and the algorithm described here yields reasonable runtimes.
Computational Experiments
With the theoretical description of the volume exchange dissimilarities established, this section shows their effectiveness in computational experiments. Our approach is a modification of an earlier study [21] which proposed a practical framework for the comparison of polycrystalline microstructures. The key idea was to represent a microstructure as a family of window probability distributions parameterized by the window size. Windows were computationally represented as voxelized two-dimensional cell structures with an associated measure having a value of one on cell boundary voxels and zero on cell interior voxels. A window distance was defined as the unbalanced Wasserstein distance between the associated measures using the taxicab distance on the underlying voxel space; this is referred to as the grain boundary distance below. For a given window size, an empirical window distribution was sampled from each of the microstructures being compared. A microstructure distance was then defined as the Wasserstein distance between the associated empirical window distributions using the grain boundary distance on the underlying window space. This framework was applied to a dataset of synthetic microstructures, and was shown to be able to distinguish microstructures belonging to different classes and to match sampled windows to the most likely originating microstructures.
Our approach here follows that of Ref. [21] but with (i) the grain boundary distance on windows replaced by the volume exchange metric and volume exchange dissimilarity and (ii) the Wasserstein distance on empirical window distributions replaced by the energy distance (defined below). The use of the energy distance also effectively resolves an issue reported in Ref. [21] of there being a non-zero self-distance due to the stochasticity of the empirical window sampling. A more comprehensive computational study comparing the effectiveness of the volume exchange dissimilarities and the grain boundary distance is intended to be the subject of a forthcoming companion paper.
We use the same set of three-dimensional microstructures as in Ref. [21]. Figure 8 shows representative two-dimensional sections of the five microstructures. EI is considered the base equiaxed structure, with the other four deviating from EI in ways that correspond to realizable physical processes. The larger grain size of EII could be formed by an isothermal anneal, and the large grains in BII could indicate a process of abnormal grain growth. The grains of RI are highly anisotropic. as would occur during a rolling process, and BI contains small grains that could be inclusions from a precipitation reaction. These represent five natural and geometrically distinct microstructure classes, and the purpose of our computational experiments is to show that the volume exchange dissimilarities can be used to reliably distinguish microstructures of different classes.
Figure 8. Representative areas (80 × 80 pixels) of microstructures generated in DREAM.3D after Ref. [21]. From left to right, EI is the base equiaxed structure, EII is equiaxed with large grains, BII is the base structure with large inclusions, RI is rolled with highly anisotropic grains, and BI is the base structure with small inclusions.
The sampling procedure to construct the empirical window distribution is adapted from Ref. [21]. Starting with a three-dimensional microstructure in a large cube, two-dimensional microstructures are constructed by intersecting the cube with planes in uniform increments along a single axis, with the increment large enough to minimize the possibility of correlations. While three-dimensional synthetic cell structures could be represented using samples of three-dimensional windows, real data is most often found in the form of two-dimensional slices. Square windows of a fixed width chosen to be 20 pixels are sampled uniformly from the two-dimensional slices, rejecting windows that overlap with one of the previously sampled windows.
After sampling windows from the five classes of synthetic microstructures, we compare the sets of sampled windows using the energy distance [22] which is commonly used in statistical literature and applications, see [23, 24].
Definition 28. Let ( Z , d Z ) (Z,d_Z) ( Z , d Z ) be a metric space and let μ \mu μ and ν \nu ν be probability measures on Z Z Z . The energy distance between μ \mu μ and ν \nu ν is
D ( μ , ν ) = 2 E μ × ν [ d Z ( X , Y ) ] − E μ × μ [ d Z ( X , X ′ ) ] − E ν × ν [ d Z ( Y , Y ′ ) ] (37) D(\mu,\nu)=\sqrt{2\mathbb{E}_{\mu\times\nu}[d_Z(X,Y)]-\mathbb{E}_{\mu\times\mu}[d_Z(X,X')]-\mathbb{E}_{\nu\times\nu}[d_Z(Y,Y')]} \tag*{(37)} D ( μ , ν ) = 2 E μ × ν [ d Z ( X , Y )] − E μ × μ [ d Z ( X , X ′ )] − E ν × ν [ d Z ( Y , Y ′ )] (37) where X , X ′ ∼ μ X,X' \sim\mu X , X ′ ∼ μ and Y , Y ′ ∼ ν Y,Y' \sim\nu Y , Y ′ ∼ ν .
The energy distance is a metric on probability distributions on ( Z , d Z ) (Z,d_Z) ( Z , d Z ) if and only if d Z d_Z d Z has strong negative type, which is stronger than requiring that d Z d_Z d Z is conditionally negative definite.[25] However, by Prop. 26 the one-to-one volume exchange metric is not conditionally negative definite and by Prop. 25 the many-to-many volume exchange dissimilarity is not even a metric. As such, the energy distance is not theoretically guaranteed to be a metric nor even be non-negative. However, the use of Szekely’s two sample energy statistic [22, Definition 6.1] produces excellent energy distance results in practice.
The energy distance is estimated by letting X = { x 1 , … , x n } X = \{x_1, \ldots, x_n\} X = { x 1 , … , x n } and Y = { y 1 , … , y n } Y = \{y_1, \ldots, y_n\} Y = { y 1 , … , y n } be windows sampled by the procedure described above. We first compute a pairwise dissimilarity matrix between the two collections of windows using one of the two volume exchange dissimilarities defined above. An example of such a pairwise dissimilarity matrix is given in Figure 9 where the d D V 1 d_{\mathrm{DV}}^{1} d DV 1 is evaluated between the window distributions for EI and EII. From these pairwise distances, the following V V V -statistics are defined which represent the average dissimilarities between pairs of samples:
Figure 9. Pairwise dissimilarity matrix for 40 2 D 2D 2 D windows with the first 20 windows (rows) sampled from EI and the second 20 sampled from EII, with the volume exchanges between two pairs of windows shown in gray on the sides. Numerical values are the d D V d_{\mathrm{DV}} d DV volume exchange distance between the corresponding windows and are normalized by window area to be bounded between 0-1. Notice the resemblance to a block matrix with different average dissimilarity values as indicated by the red lines. The empirical energy distance in Eq. (41) effectively finds the difference between mean values of the diagonal and off-diagonal blocks.
μ X Y = 1 n 2 ∑ i = 1 n ∑ j = 1 n d D V ( x i , y j ) (38) \mu_{\mathrm{XY}} = \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{\mathrm{DV}}(x_i,y_j) \tag*{(38)} μ XY = n 2 1 i = 1 ∑ n j = 1 ∑ n d DV ( x i , y j ) (38)
μ X = 1 n 2 ∑ i = 1 n ∑ j = 1 n d D V ( x i , x j ) (39) \mu_{\mathrm{X}} = \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{\mathrm{DV}}(x_i,x_j) \tag*{(39)} μ X = n 2 1 i = 1 ∑ n j = 1 ∑ n d DV ( x i , x j ) (39)
μ Y = 1 n 2 ∑ i = 1 n ∑ j = 1 n d D V ( y i , y j ) (40) \mu_{\mathrm{Y}} = \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{\mathrm{DV}}(y_i,y_j) \tag*{(40)} μ Y = n 2 1 i = 1 ∑ n j = 1 ∑ n d DV ( y i , y j ) (40)
The energy distance is then estimated from Eq. (37) as
ε ( X , Y ) = 2 μ X Y − μ X − μ Y (41) \varepsilon(X,Y) = \sqrt{2\mu_{\mathrm{XY}}-\mu_{\mathrm{X}}-\mu_{\mathrm{Y}}} \tag*{(41)} ε ( X , Y ) = 2 μ XY − μ X − μ Y (41)
Figure 10 illustrates the pairwise energy distance estimates for samples of 1200 windows from the five synthetic microstructures. EII is the furthest from all other microstructures except R I RI R I , and this makes sense since EII has substantially larger grains and the volume exchange dissimilarities are sensitive to variations in cell area. In contrast, observe that BII is the closest non diagonal entry to EI, which is likely due to both microstructures having the same base cell-structure while BII’s large inclusions slightly drive up the average distance. However, notice that BI also shares the same primary structure as EI but has a significantly higher energy distance to EI relative to BII. This likely stems from the average cost to match a cell in EI to a cell in BI being inflated by the area of the inclusions that are embedded within the BI base grains. Finally, the nonzero energy distance between EI and RI likely occurs because cells from EI must compress and stretch to match a cell in RI.
Figure 10. Dissimilarity matrices between window distributions. Empirical 2 D 2D 2 D window distributions were generated by sampling 1200 windows uniformly at random from the respective micrographs without replacement. Entries were computed using the energy distance in Eq. (41) . The left matrix uses d D V 1 d_{DV}^{1} d D V 1 while the right matrix uses d D V 2 d_{DV}^{2} d D V 2 . Notice that both matrices satisfy the triangle inequality and that entries along the diagonal are consistently smaller than non-diagonal entries.
One can notice that both the one-to-one volume exchange metric and many-to-many volume exchange dissimilarity yield similar heatmaps in Figure 10 . This motivates the use of the one-to-one volume exchange metric as a computationally cheaper alternative to the many-to-many volume exchange dissimilarity.
Figure 11 shows the convergence of the energy distance statistics. Notice that as the number of samples is increased the relative ordering of energy distances remains stable even for small samples of windows while the self-distance decreases towards zero. Also, it appears that the limiting distance values satisfy the triangle inequality. The fact that self energy distances are less than all other distances support the use case of the volume exchange informed energy distance as a way to create hypothesis tests for microstructure validation procedures. Finally, since the relative ordering of the microstructure distances are stable, one does not need to sample a high number of windows, like we do, in practice.
Figure 11. Subplots showing the energy distance from the indicated microstructure distribution to every microstructure distribution including itself. The top plots use d D V 1 d_{\mathrm{DV}}^{1} d DV 1 and the bottom plots use d D V 2 d_{\mathrm{DV}}^{2} d DV 2 . Each data point represents the average of 5 energy distances computed across different sets of 2D windows. Error bars indicate ± 1 \pm1 ± 1 standard deviation. Notice that the energy distance maintains a consistent ordering for at least 100 sampled windows. Moreover, the distance appears to converge to zero only for self-distances.
We also compared 3D windows sampled from the synthetic microstructures using the same pipeline. Only d D V 1 d_{\mathrm{DV}}^{1} d DV 1 was computed, as d D V 2 d_{\mathrm{DV}}^{2} d DV 2 was slow to compute. These results can be found in Figure 12 . The largest visual discrepancy between the results using 2D windows versus 3D windows comes from the pairwise distances of micrographs between RI and the remaining structures. This likely stems from 3 D 3D 3 D windows capturing RI’s geometric anisotropy from all three axes.
Figure 12. Top left: energy distance heatmap using d D V 1 d^{1}_{DV} d D V 1 between 3D window distributions. 1200 windows of dimension 20 × 20 × 20 20 \times20 \times20 20 × 20 × 20 were sampled uniformly at random from the respective micrographs without replacement. Top right: a visualization of d D V 1 d^{1}_{DV} d D V 1 between 3D windows sampled from EI and EII. Note that for visualization purposes, the 3D windows were scaled uniformly to 40 × 40 × 40 40 \times40 \times40 40 × 40 × 40 and an overlay of the union of the grain boundaries between the two windows is shown in gray. Bottom: Convergence plots of the energy distance using d D V 1 d^{1}_{DV} d D V 1 on 3D window distributions.
The code and data used to generate the Figure 10 , Figure 11 , and Figure 12 can be found on GitHub along with additional documentation regarding the implementation.
LLM Usage Disclosure
Any use of generative AI in this manuscript adheres to ethical guidelines for use and acknowledgment of generative AI in academic research [26]. Each author has made a substantial contribution to the work, which has been thoroughly vetted for accuracy, and assumes responsibility for the integrity of their contributions. LLMs were used to implement the code to compute the integer program in Equation (36) , to generate batch scripts to parallelize the computation of pairwise distances, generate Tikz code for Figure 6 , and to modify Figure 2 to create Figure 3 . They were also used to proofread a draft of the manuscript and check for mathematical errors. LLMs were not otherwise used at any stage of the theoretical work or the writing process.
Acknowledgments
S.P. and B.S. are grateful for the support of the National Science Foundation under Award No. 2232967. J.K.M. is grateful for the support of the National Science Foundation under Award No. 2232968.
[? ] Harold W Kuhn. The Hungarian method for the assignment problem. Naval research logistics quarterly , 2(1-2):83–97, 1955.
[? ] Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review , 33(1):60–100, 1991.
[? ] Dylan Miley, Ethan Suwandi, Benjamin Schweinhart, and Jeremy K. Mason. Microstructure classification and the polycrystalline microstructure state space. Acta Materialia , 296:121219, 2025. ISSN 1359-6454. doi: https://doi.org/10.1016/j.actamat.2025.121219. URL https://www.sciencedirect.com/science/article/pii/S1359645425005063.
[? ] Gábor J. Székely and Maria L. Rizzo. Energy statistics: A class of statistics based on distances. Journal of Statistical Planning and Inference , 143(8):1249–1272, 2013. ISSN 0378-3758. doi: https://doi.org/10.1016/j.jspi.2013.03.018. URL https://www.sciencedirect.com/science/article/pii/S0378375813000633.
[? ] Simon Mak and V. Roshan Joseph. Support points. The Annals of Statistics , 46(6A):2562 – 2592, 2018. doi: 10.1214/17-AOS1629. URL https://doi.org/10.1214/17-AOS1629.
[? ] Florian Ziel. The energy distance for ensemble and scenario reduction. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , 379(2202):20190431, 06 2021. ISSN 1364-503X. doi: 10.1098/rsta.2019.0431. URL https://doi.org/10.1098/rsta.2019.0431.
[? ] Russell Lyons. Distance covariance in metric spaces. The Annals of Probability , pages 3284–3305, 2013.
[? ] Sebastian Porsdam Mann, Anuraag A Vazirani, Mateo Aboy, Brian D Earp, Timo Minssen, I Glenn Cohen, and Julian Savulescu. Guidelines for ethical use and acknowledgement of large language models in academic writing. Nature Machine Intelligence , 6(11):1272–1274, 2024.
Department of Mathematical Sciences, The University of Texas at El Paso, El Paso, TX 79968, USA
Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, USA
Department of Materials Science and Engineering, University of California, Davis, Davis, CA 95616, USA
Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, USA
Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, USA