# Flips in Two-dimensional Hypertriangulations111 Work by all authors but the
second is supported by the European Research Council (ERC), grant no. 788183,
by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31,
and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund
(FWF), grant no. I 02979-N35. Work by the second author is partially supported
by the Alexander von Humboldt Foundation.

Herbert Edelsbrunner  ISTA (Institute of Science and Technology Austria),
Klosterneuburg, Austria<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Alexey Garber  School of
Mathematical and Statistical Sciences, University of Texas Rio Grande Valley,
Brownsville, Texas, USA<EMAIL_ADDRESS>Mohadese Ghafari  Department
of Mathematical Sciences, Sharif University of Technology, Tehran, Iran,
<EMAIL_ADDRESS>Teresa Heiss  ISTA (Institute of Science and
Technology Austria), Klosterneuburg, Austria<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Morteza Saghafian  ISTA
(Institute of Science and Technology Austria), Klosterneuburg, Austria,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study flips in hypertriangulations of planar points sets. Here a level-$k$
hypertriangulation of $n$ points in the planes is a subdivision induced by the
projection of a $k$-hypersimplex, which is the convex hull of the barycenters
of the $(k-1)$-dimensional faces of the standard $(n-1)$-simplex. In
particular, we introduce four types of flips and prove that the level-2
hypertriangulations are connected by these flips.

###### keywords:

Hypertriangulations, coherent hypertriangulations, order-$k$ Delaunay
triangulations, flip-connectivity.

##  1 Introduction

Triangulations appear in many fields of pure and applied mathematics, and they
go back to the study of the Catalan numbers by Euler and Goldbach in the early
18th century [23], if not further. Flips were introduced by Wagner [33] as a
tool to study how triangulations change. In particular, he proved that for a
planar set, the family of triangulations is flip-connected. This fact was
later exploited by Lawson [17] to construct triangulations algorithmically for
the purpose of surface interpolation. Ever since, flip-connectivity has become
a standard topic in discrete and computational geometry. In the plane, flip-
connectivity leads to efficient algorithms for constructing Delaunay
triangulations and to proofs of extremal properties, for example that among
all triangulations of a finite set the Delaunay triangulation maximizes the
minimum angle [32].

Beyond two dimensions, flip-connectivity is a more challenging concept. For
example, the greedy algorithm that flips a locally non-convex configuration
succeeds in constructing the Delaunay triangulation in the plane [17], but can
get stuck in local minima in three dimensions; see [15] for examples. However,
a more limited protocol that inserts points incrementally and repairs the
Delaunay triangulation after every insertion also succeeds in three dimensions
[16] and extends to higher dimensions and to coherent triangulations [10].
Note that the latter are known in the literature under a variety of names,
including _Laguerre_ , _regular_ , and _weighted Delaunay triangulations_.
While flip-connectivity in three dimensions is still an open question, Santos
[29] has exhibited a configuration in six dimensions whose family of
triangulations is not flip-connected. We refer to [7, 14, 18, 19, 31, 34] and
references therein for a multitude of results on flip-connectivity in a
variety of settings.

In this paper, we study flips in the family of hypertriangulations of a finite
set of $n$ points in the plane. These are triangulations induced by
projections of an $(n-1)$-dimensional hypersimplex to the plane. To explain
these concepts, we fix an integer $k$ between $1$ and $n-1$, called the
_level_ , and we write $\Delta_{n}^{(k)}$ for $k$-fold scaling of the convex
hull of the barycenters of the $(k-1)$-dimensional faces of the standard
$(n-1)$-simplex, $\Delta_{n}=\Delta_{n}^{(1)}$. Correspondingly, we write
${{A}^{({k})}}$ for the set of $k$-fold sums of the points in the given set of
$n$ points, $A={{A}^{({1})}}$. The projection fixes a bijection between the
vertices of $\Delta_{n}$ and the points of $A$ and, by construction, maps the
vertices of $\Delta_{n}^{(k)}$ to the points of ${{A}^{({k})}}$. The
hypertriangulations follow by selecting and projecting appropriate subsets of
the $2$-dimensional faces of $\Delta_{n}^{(k)}$. The subclass of coherent
level-$k$ hypertriangulations are also known as _weighted order- $k$ Delaunay
triangulations_, defined by generalizing order-$k$ Delaunay triangulations [3]
to the weighted setting.

Hypertriangulations were introduced by Olarte and Santos [22] as a tool to
study the Baues problem for families of plabic graphs related to the totally
positive Grassmannian [25]. The case $k=1$ corresponds to the family of usual
triangulations of the set $A$. In the general setting of subdivisions induced
by projection between two polytopes, the notion of flips comes from the Baues
poset, see [28, 30]. We refer to these as _combinatorial_ or _Baues flips_ as
it seems difficult to give a geometric description in all possible cases, even
for a generic projection. Primarily in connection to the Baues problem, the
connectivity of the flip graph for various settings related to the
subdivisions induced by projections of polytopes has been studied in [2, 20,
27], where positive as well as negative results are described.

Noting that we restrict ourselves to generic point sets in the plane, here is
the outline of this paper: Section 2 follows Olarte and Santos [22] and
introduces level-$k$ hypertriangulations of a point set of $n$ points, $A$, as
tight subdivisions induced by the projection of the hypersimplex
$\Delta_{n}^{k}$. In particular, we give a combinatorial description of such
triangulations without using the associated projection. We also define the
more general hypersimplicial subdivisions and sketch a connection to fiber
polytopes [5]. Section 3 introduces the four types of flips for level-$k$
hypertriangulations. Notably, these flips are geometric, they do not depend on
the level $k$, and they include the classic flips for triangulations of planar
point sets [6].

Section 4 proves the main result of this paper: that the family of level-2
hypertriangulations of every (generic) planar point set is flip-connected. The
main tool in the proof is the aging function for triangles of
hypertriangulations defined in Section 4.1.

Section 5 discusses connections of flips in hypertriangulations to plabic
graphs studied by Postnikov [24, 25] and Galashin [11], and reformulates their
results in the language of flips. It also discusses flips within the family of
coherent triangulations and the relation to the fiber polytope. Section 6
concludes the paper with a discussion of possible further research.

##  2 Introduction to Hypertriangulations

This section explains the main object of study: the hypertriangulations of a
finite point set. To begin, we give an informal introduction to the subject,
drawing connections to the theory of fiber polytopes along the way, and follow
up with formal definitions thereafter.

###  2.1 Level-$k$ Hypertriangulations

Let $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ be a generic set of $n$ points in
${{\mathbb{R}}}^{2}$. Write $[n]=\\{1,2,\ldots,n\\}$, and for a subset
$I\subseteq[n]$, let $a_{I}=\sum_{i\in I}a_{i}$ be the vector sum of the
points with index in $I$. Fixing a parameter $k\in[n-1]$, we write
${{A}^{({k})}}=\\{a_{I}\mid I\subseteq[n],{{|}{I}{|}}=k\\}$ for the $k$-fold
sums and consider all _partial triangulations_ of ${{A}^{({k})}}$, by which we
mean the decompositions of the convex hull of ${{A}^{({k})}}$ into triangles,
each formed by connecting a subset of the points with straight edges. For the
time being, assume that no three points of ${{A}^{({k})}}$ are collinear.

######  Definition 2.1.

A _level- $k$ hypertriangulation of $A$_ is a partial triangulation of
${{A}^{({k})}}$ so that

  * (V)

every vertex is of the form $a_{I}$, with ${{|}{I}{|}}=k$, and

  * (E)

every edge connects two vertices, $a_{I}$ and $a_{J}$, that satisfy
${{|}{I\cap J}{|}}=k-1$.

$235$$123$$136$$135$$156$$146$$134$$356$$126$$125$$145$$124$$256$$236$$234$$346$$345$$456$$245$$246$$3$$6$$5$$1$$2$$4$

Figure 1: _Left:_ $n=6$ points in the plane. _Right:_ the $\binom{n}{3}=20$
triple sums of these points together with a triangulation of $12$ of the $20$
points. The three vertices of every _black_ triangle share one point in their
sums, and the three vertices of every _white_ triangle share two.

See Figure 1 for a level-$3$ hypertriangulation of $6$ points in
${{\mathbb{R}}}^{2}$ as an example. The labels of the vertices indicate how
they are obtained from the $6$ points shown on the left. Note that some of the
$20$ points in ${{A}^{({3})}}$ are not vertices of the displayed
hypertriangulation. The requirement on the endpoints of every edge implies a
similar requirement on the vertices of every triangle:

######  Definition 2.2.

Let $\Delta=a_{I}a_{J}a_{K}$ be a triangle whose vertices and edges satisfy
conditions (V) and (E). Then either $|I\cap J\cap K|=k-1$, in which case we
call $\Delta$ a _white triangle_ , or $|I\cap J\cap K|=k-2$, in which case we
call $\Delta$ a _black triangle_.

Note that white triangles exist for $1\leq k\leq n-2$ and black triangles
exist for $2\leq k\leq n-1$. For a given triangulation, $T$, we write $W(T)$
and $B(T)$ for the sets of white and black triangles, respectively. In the
example in Figure 1, there are $8$ triangles of each color.

###  2.2 Hypersimplicial Subdivisions

The following interpretation of the above concepts gives an equivalent
description within the theory of fiber polytopes and induced subdivisions. We
refer to [35, Chap. 9] and [6] for a comprehensive introductions to this
theory.

Write $\Delta_{n}={{\rm
conv}{\\{e_{1},e_{2},\ldots,e_{n}\\}}}\subseteq{{\mathbb{R}}}^{n}$ for the
standard $(n-1)$-simplex, and more generally $\Delta_{n}^{(k)}={{\rm
conv}{\\{e_{I}\mid I\subseteq[n],{{|}{I}{|}}=k\\}}}$ for the $k$-th standard
$(n-1)$-dimensional hypersimplex. Let $\pi\colon\Delta_{n}\to{{\rm conv}{A}}$
be the (linear) projection defined by $\pi(e_{i})=a_{i}$, and following Olarte
and Santos [22], we extend this to the projection
$\pi\colon\Delta_{n}^{(k)}\to{{\rm conv}{{{A}^{({k})}}}}$. We get tilings of
${{A}^{({k})}}$ by projecting subsets of the $2$-dimensional faces of
$\Delta_{n}^{(k)}$ instead of the entire hypersimplex. By construction, the
label of each vertex of $\Delta_{n}^{(k)}$ is a subset of $k$ integers in
$[n]$, the endpoints of each edge have labels that differ in exactly one
integer, and the $2$-dimensional faces are triangles and therefore satisfy the
condition on the vertex labels given in Definition 2.2. Each such tiling is
called a _hypertriangulation_ in [22], and it agrees with our notion of
hypertriangulation given in Definition 2.1 in the generic setting.

######  Remark 2.3.

According to our current definition of a generic set, $A$, no three points of
${{A}^{({k})}}$ are collinear, for any $k\in[n-1]$. This implies that the
projection of any $2$-dimensional face of $\Delta_{n}^{(k)}$ is a triangle.
This property also holds if we weaken our notion of genericity to requiring
that no three points of $A$ are collinear, and this is the definition we will
use from now on. However, in this case, two or more points of ${{A}^{({k})}}$
may coincide, but since they have different labels, we still treat them as
different points. In the presence of coinciding points, we require that at
most one of these points is used in any one triangulation. Equivalently, we
require that the hypertriangulation remains a hypertriangulation if we perturb
the points in $A$ by any sufficiently small amount. For an example see Figure
2, which shows two geometrically identical projections of four $2$-dimensional
faces of the octahedron, $\Delta_{4}^{(2)}$. Since the respective central
vertices have different labels ($13$ versus $24$), the two hypertriangulations
are considered different.

$34$$23$$34$$23$$12$$14$$12$$14$$13$$24$

Figure 2: _Left:_ two hypertriangulations of four points arranged as the
vertices of a diamond in the plane. _Right:_ one of the hypertriangulations as
the projection of an octahedron.

######  Definition 2.4.

A _level- $k$ hypersimplicial subdivision_ of $A$ is a tiling of ${{\rm
conv}{{{A}^{({k})}}}}$ with projected faces of $\Delta_{n}^{(k)}$ that remains
a tiling under any sufficiently small perturbation of $A$.

Note that Definition 2.4 allows for projections of faces of dimension larger
than $2$, which are convex polygons with possibly more than three edges. In
contrast to hypertriangulations, Conditions (V) and (E) of Definition 2.1 do
not suffice to distinguish hypersimplicial subdivisions from other tilings of
$A$. Take for example a set $A$ of four points whose convex hull is a
triangle. Then ${{\rm conv}{{{A}^{({2})}}}}$ is a convex hexagon, which we may
tile as shown in the left panel of Figure 3. All edges satisfy Condition (E),
but this tiling cannot be obtained as projection of faces of the octahedron
$\Delta_{4}^{(2)}$.

$34$$12$$13$$23$$24$$14$$36$$34$$45$$25$$13$$56$$24$$15$$12$$23$$26$$16$$35$$46$$14$

Figure 3: _Left:_ a subdivision of the $2$-fold sums of four points that is
not a hypersimplicial subdivision of the six points. _Right:_ a subdivision of
the $2$-fold sums of the six points in Figure 1 that can be interpreted as
hypersimplicial in more than one way.

Similarly, two different hypersimplicial subdivisions may lead to
geometrically identical tilings. See the right panel in Figure 3, in which we
cannot distinguish between the lower right triangle being the projection of a
tetrahedron or of its $2$-dimensional face whose projected image (which is the
triangle) contains the projected fourth vertex. These two choices are treated
as different subdivisions, with the latter being a refinement of the former.
To disambiguate the situation, we will draw the projection of the fourth
vertex only if the triangle is the projection of the tetrahedron but not if it
is the projection of a $2$-dimensional face of the tetrahedron.

###  2.3 Coherent Hypersimplicial Subdivisions and Fiber Polytopes

Within all hypersimplicial subdivisions of a finite set,
$A\subseteq{{\mathbb{R}}}^{2}$, the coherent hypersimplicial subdivisions form
a privileged subfamily. These subdivisions are constructed as lower boundaries
of convex polytopes obtained by lifting the points of $A^{(k)}$ according to a
linear function on ${{\mathbb{R}}}^{n}$. Let
$h\colon{{\mathbb{R}}}^{n}\to{{\mathbb{R}}}$ be such a linear function, and
write $h_{i}=h(\pi^{-1}(a_{i}))$ for the value at the preimage of a point
$a_{i}\in A$. For every $k$, the value at a vertex of $\Delta_{n}^{(k)}$ is
the sum of the values of the corresponding $k$ vertices of $\Delta_{n}$. We
therefore write $h_{I}=h(\pi^{-1}(a_{I}))=\sum\nolimits_{i\in I}h_{i}$ for
every $I\subseteq[n]$.

######  Definition 2.5.

Let $A_{h}^{(k)}=\\{(a_{I},h_{I})\mid|I|=k\\}$ be the _$h$ -lifted_ points at
level $k$ and note that these are points in ${{\mathbb{R}}}^{3}$. The
associated _coherent hypersimplicial subdivision_ , denoted $T^{(k)}(A,h)$, is
the natural projection (which removes the last coordinate) of the lower
boundary of ${{\rm conv}{A_{h}^{(k)}}}$ to ${{\rm conv}{A^{(k)}}}$. In the
particular case in which the lower boundary has only triangular faces, we call
its projection a _coherent hypertriangulation_ of $A$.

The corresponding _fiber polytope_ , denoted $\mathcal{F}(\Delta_{n}^{(k)}\to
A^{(k)})$, is the set of points

$\frac{1}{\mathrm{area}({{\rm conv}{A^{(k)}}})}\int_{{{\rm
conv}{A^{(k)}}}}f(x)\,{\rm d}x,$

over all continuous functions $f\colon{{\rm
conv}{A^{(k)}}}\to\Delta_{n}^{(k)}$ such that $\pi(f(x))=x$ for all $x\in{{\rm
conv}{A^{(k)}}}$. Note that this is a subset of
$\Delta_{n}^{(k)}\subseteq{{\mathbb{R}}}^{n}$. The vertices of the fiber
polytope correspond to coherent hypertriangulations, and the faces correspond
to all coherent subdivisions; see [22] and [5] for more details.

Because $\Delta_{n}^{(k)}$ is a complex of hypersimplices, we can use the
following equivalent definition, which resembles the one of the secondary
polytope associated with the point set $A$; see [13].

######  Definition 2.6.

Set $e_{I}=\sum_{i\in I}e_{i}$ for each $I\subseteq[n]$, and write ${{\rm
GKZ}{({\Delta})}}=\operatorname{area}(\Delta)\cdot\tfrac{1}{3}(e_{I}+e_{J}+e_{K})$
for every triangle $\Delta=a_{I}a_{J}a_{K}$. Then the corresponding _fiber
polytope_ , or _level- $k$ hypersecondary polytope_ of $A$, denoted
$\mathcal{F}^{(k)}(A)$, is the convex hull of the point set

$\left\\{{{\rm GKZ}{({T})}}=\frac{1}{\mathrm{area}({{\rm
conv}{A^{(k)}}})}\sum\nolimits_{\Delta\in T}{{\rm GKZ}{({\Delta})}}\mid
T\text{ is a level-$k$ hypertriangulation of $A$}\right\\}.$

##  3 Flips in Hypertriangulations

The level-$1$ hypertriangulations of a finite set,
$A\subseteq{{\mathbb{R}}}^{2}$, are commonly called the (partial)
triangulations of $A$. Flips are the elementary operations that transform one
triangulation of $A$ to another. In the generic situation, there are two
types: the first substitutes one diagonal of a convex quadrangle by the other,
and the second subdivides a triangle into three by adding a vertex or coarsens
by removing a degree-$3$ vertex; see the Type-I and Type-II flips in Figure 5.
For just four points the flips provide transitions between the only
triangulations on these points. As shown in [14], these two operations suffice
to transform any triangulation to any other triangulation of $A$.

This section introduces similar operations for level-$k$ hypertriangulations
in ${{\mathbb{R}}}^{2}$. Before giving the formal definitions, we take a look
at configurations of just four points, for which our flips appear naturally.

###  3.1 Hypertriangulations of Four Points

For $n=4$ points in ${{\mathbb{R}}}^{2}$, we have level-$k$
hypertriangulations for $k=1,2,3$. In the generic case, there are only two
combinatorially different configurations of four points: the vertices of a
convex quadrangle, or the vertices of a triangle with the fourth point inside
the triangle. We refer to them as the _convex configuration_ and the _non-
convex configuration_ , respectively. As illustrated in Figure 4, we have two
hypertriangulations for each $k$ and each of the two configurations, so twelve
hypertriangulations altogether.

$4$$123$$13$$234$$1$$1$$3$$2$$4$$4$$3$$2$$12$$14$$12$$14$$34$$23$$34$$23$$123$$234$$134$$124$$123$$234$$134$$124$$124$$234$$134$$134$$124$$23$$24$$12$$14$$13$$34$$34$$23$$24$$12$$14$$13$$1$$3$$2$$3$$2$$1$$24$

Figure 4:  The two configurations of four points in ${{\mathbb{R}}}^{2}$ and
their hypertriangulations: convex configuration in _top row_ and non-convex
configuration in _bottom row_. _From left to right:_ the two level-$1$,
level-$2$, and level-$3$ hypertriangulations for each configuration. Observe
that the squares in the _upper middle_ can be more general parallelograms so
that the respective central fifth vertices are not at the same geometric
location. Similarly, the convex hexagons in the _lower middle_ are not
necessarily regular but are necessarily centrally symmetric.

  * •

For $k=1$, the vertices are the original points, and all triangles are white.

  * •

For $k=2$, there are six points, each the sum of two points in $A$. If $A$ is
a convex configuration, the convex hull of ${{A}^{({2})}}$ is a parallelogram
and the remaining two points lie inside the parallelogram. There are only two
hypertriangulations, each choosing one of the two extra points as a vertex and
decomposing the parallelogram into two white and two black triangles. If $A$
is a non-convex configuration, the points in ${{A}^{({2})}}$ are the vertices
of a centrally symmetric convex hexagon, and there are again only two
hypertriangulations.

  * •

For $k=3$, the situation is similar to the case $k=1$, except that all
triangles are black.

The six pairs of hypertriangulations of four points inspire our definition of
flips for hypertriangulations in ${{\mathbb{R}}}^{2}$.

###  3.2 Flips

We introduce four types of flips in hypertriangulations; all illustrated in
Figure 5. A flip preserves the level of the hypertriangulation, so the
vertices and edges it introduces must satisfy Conditions (V) and (E) of
Definition 2.1.

\begin{picture}(8574.0,3451.0)(2464.0,-7010.0)\end{picture}

Figure 5:  The four types of flips in hypertriangulations. Type-I and Type-II
flips apply to all white or all black triangles, while Type-III and Type-IV
flips involve white and black triangles before and also after the flip.

######  Definition 3.1.

A _Type-I flip_ removes two triangles that share an edge and whose union is a
convex quadrangle, and it adds the other two triangles whose union is the same
quadrangle. The four triangles, two before and two after the flip, are either
all white or all black.

A _Type-II flip_ replaces a triangle by three triangles sharing a vertex
inside the removed triangle or, in the other direction, replaces the three
triangles sharing a degree-$3$ vertex with a single triangle. The four
triangles, before and after the flip, are either all white or all black.

A _Type-III flip_ applies to a parallelogram decomposed into four triangles,
which alternate between white and black around the shared vertex, and replaces
these triangles by their reflections through the center of the parallelogram.
The reflection also switches the colors.

A _Type-IV flip_ applies to a centrally symmetric convex hexagon decomposed
into four triangles, one in the middle with a color that is different from the
shared color of the surrounding three triangles. The flip replaces the four
triangles by their reflections through the center of the hexagon, and the
reflection switches the colors, as before.

######  Remark 3.2.

Explicitly requiring colors of triangles and Condition (E) of edges is
sometimes excessive. For example, if two triangles have the same color, share
an edge, and form a convex quadrangle, then Condition (E) is necessarily
satisfied by the new edge. Similarly, if a vertex is shared by a cycle of four
triangles with alternating colors, then these four triangles can be replaced
by a Type-III flip. On the other hand, for Type-II and Type-IV flips,
Condition (E) needs to be taken into account at least in one direction.

######  Example 3.3.

Take another look at Figure 1, which shows a level-$3$ hypertriangulation of
six points in ${{\mathbb{R}}}^{2}$. It is chosen so that all different types
of flips can be applied. On the upper left, we see three white triangles that
can be replaced by a single white triangle in a Type-II flip. Below them, we
see three black triangles that can be replaced by a single black triangle in
another Type-II flip. In the upper middle, we see a hexagonal region with a
black triangle surrounded by three white triangles, which can be replaced by a
white triangle surrounded by three black triangles in a Type-IV flip. After
applying this flip, we get a convex quadrangle decomposed into two black
triangles, which can be replaced by two other black triangles in a Type-I
flip. Below that hexagonal region, we see another with a white triangle
surrounded by three black triangles, and after applying a Type-IV flip, we get
an elongated convex quadrangle decomposed into two white triangles, which can
be replace by two other white triangles in another Type-I flip. Finally on the
right, we see a parallelogram whose triangles alternate between black and
white, which can be replaced by four other triangles in a Type-III flip.

##  4 Level-2 Hypertriangulations

This section proves that for every generic point set,
$A\subseteq{{\mathbb{R}}}^{2}$, the collection of level-$2$
hypertriangulations is flip-connected. The main tool used for this purpose is
the aging function and its inverse. This function appeared under different
names in the work of Olarte and Santos [22] on hypertriangulations, of
Galashin [11] and Balitskiy, Wellman [4] on plabic graphs, and of
Edelsbrunner, Osang [9] on a fast algorithm for level-$k$ Delaunay mosaics.

###  4.1 Aging Function

The _aging function_ , $F$, maps a white triangle with vertices in
${{A}^{({k})}}$ to a black triangle with vertices in ${{A}^{({k+1})}}$.
Specifically, if ${{|}{I}{|}}={{|}{J}{|}}={{|}{K}{|}}=k$ and ${{|}{I\cap J\cap
K}{|}}=k-1$, then

$F(a_{I}a_{J}a_{K})=a_{I\cup J}a_{J\cup K}a_{K\cup I}.$

Indeed, we have ${{|}{I\cup J}{|}}={{|}{J\cup K}{|}}={{|}{K\cup I}{|}}=k+1$
and ${{|}{(I\cup J)\cap(J\cup K)\cap(K\cup I)}{|}}=k-1$, so the image of
$a_{I}a_{J}a_{K}$ under $F$ is black. The inverse of the aging function is
well defined on the black triangles: if
${{|}{I}{|}}={{|}{J}{|}}={{|}{K}{|}}=k$ and ${{|}{I\cap J\cap K}{|}}=k-2$,
then

$F^{-1}(a_{I}a_{J}a_{K})=a_{I\cap J}a_{J\cap K}a_{K\cap I}.$

Recall that $W(T)$ and $B(T)$ are the white and black triangles in $T$.
Accordingly, we write $F(W(T))$ and $F^{-1}(B(T))$ for the images under the
aging function and its inverse. With this notation, we have the following
property.

######  Lemma 4.1.

For every level-$1$ hypertriangulation, $T$, of a generic set
$A\subseteq{{\mathbb{R}}}^{2}$, there exists a level-$2$ hypertriangulation,
$U$, of $A$ such that $B(U)=F(W(T))$.

######  Proof 4.2.

Since $T$ is level-$1$, all its triangles are white. To get $F(W(T))$, we take
the midpoints of all edges in $T$ and for every triangle in $T$ draw a (black)
triangle that connects the midpoints within this triangle. After inflating the
configuration by a factor $2$, we get a subset of ${{A}^{({2})}}$ together
with a collection of black triangles; see Figure 6, which suppresses the
inflation for better visualization. The part of the convex hull of
${{A}^{({2})}}$ not covered by black trianlges is thus split into regions, and
it remains to show that all these regions can be triangulated using white
triangles only.

\begin{picture}(7981.0,2356.0)(-4327.0,-12714.0)\end{picture}

Figure 6: A level-$1$ hypertriangulation of $7$ points on the _left_ , and the
(shrunken) image of the aging function applied to its $8$ white triangles on
the _right_. The area left out by the black triangles are (shrunken) copies of
the vertex stars in the level-$1$ hypertriangulation.

The gaps between the black triangles are of two types. Each gap that is
completely surrounded by black triangles is in the shape of the star of an
internal vertex of $T$. Indeed, for every internal vertex, $a_{i}$ of $T$, the
black triangles within the star of $a_{i}$ cut out a scaled copy of the said
star, which inflates into a copy of the star. This star can be triangulated
using the vertices in its boundary, and since these vertices share $i$ as one
of their labels, all resulting triangles are white.

Each gap that is not completely surrounded by black triangles is obtained from
the star of a boundary vertex of $T$. Specifically, for every boundary vertex,
$a_{j}$ of $T$, the black triangles in its star cut out a scaled copy of the
star, which, after inflation, is intersected with ${{\rm
conv}{{{A}^{({2})}}}}$. This intersection consists of one or more possibly
non-convex polygons. The vertices of these polygons are the vertices of the
star (other than $a_{j}$), as well as vertices of ${{\rm
conv}{{{A}^{({2})}}}}$. The former share $j$ as one of their labels. To see
that this is also true for the latter, we rotate two parallel supporting
lines, one around ${{\rm conv}{A}}$ and the other around ${{\rm
conv}{{{A}^{({2})}}}}$. Whenever the second supporting line passes through a
boundary vertex that is also a vertex of one of the polygons, the first
supporting line passes through $a_{j}$. It follows that $j$ is a label of the
boundary vertex. Hence, all vertices of the polygons share $j$ as one of their
labels, and any triangulation obtained by connecting these vertices produces
only white triangles.

###  4.2 Inverse of Aging Function

The aging function can be reversed to construct the level-$1$
hypertriangulation that gives rise to a given level-$2$ hypertriangulation. To
prepare this construction, we let $U$ be a level-$2$ hypertriangulation of
$A$, and for each $a_{i}\in A$, we write $W_{i}(U)$ for the set of white
triangles in $U$, whose three vertices share the label $i$. In the forward
construction of Lemma 4.1, $W_{i}(U)$ would be the triangles re-triangulating
(part of) the star of $a_{i}$, but a priori it is not clear that $U$ can be
constructed this way. We will sometimes abuse notation and write $W_{i}(U)$
for the union of its triangles.

######  Lemma 4.3.

Let $U$ be a level-$2$ hypertriangulation of a generic set
$A\subseteq{{\mathbb{R}}}^{2}$, let $a_{i}\in A$. Assume $W_{i}(u)$ is non-
empty, and let $x$ be a point in its interior. Then all triangles in $U$ that
have a non-empty intersection with the line segment from $x$ to $2a_{i}$
belong to $W_{i}(U)$, and if $a_{i}$ lies in the interior of ${{\rm
conv}{A}}$, then $W_{i}(U)$ contains the entire line segment.

######  Proof 4.4.

We prove the case in which $a_{i}$ lies in the interior of ${{\rm conv}{A}}$.
The case of a boundary point is easier and omitted. To get a contradiction, we
assume there is a point $x\in W_{i}(U)$ such that $W_{i}(U)$ does not contain
the entire line segment from $x$ to $2a_{i}$. Hence, the line segment crosses
the boundary of $W_{i}(U)$, and we let $a_{ij}$ and $a_{ik}$ be the endpoints
of the boundary edge that crosses the line segment closest to $x$. Let $L$ be
the line that passes through $a_{ij}$ and $a_{ik}$. Since $x$ and $2a_{i}$ lie
on opposite sides of $L$, the points $2a_{j}$ and $2a_{k}$ lie on the same
side of $L$ as $x$. It follows that the entire black triangle with vertices
$a_{ij}$, $a_{ik}$, $a_{jk}$ lies on this side of $L$. But then there are
points on the line segment from $x$ to $2a_{i}$ outside $W_{i}(U)$ that are
closer to $x$ than the crossing with $L$, which is a contradiction. Hence,
$W_{i}(U)$ is star-convex and contains the entire line segment from $x$ to
$a_{i}$.

We use Lemma 4.3 to prove that the aging function allows us to go back and
forth between level-$1$ and level-$2$ hypertriangulations.

######  Lemma 4.5.

Let $U$ be a level-$2$ hypertriangulation of a generic set
$A\subseteq{{\mathbb{R}}}^{2}$. Then $F^{-1}(B(U))$ is a well defined
level-$1$ hypertriangulation of $A$.

######  Proof 4.6.

First we prove that if $a_{i}$ and $a_{j}$ are the endpoints of a side of
${{\rm conv}{A}}$, then there is exactly one triangle in $B(U)$ with vertex
$a_{ij}$. Observe that $a_{ij}$ is necessarily a vertex of ${{\rm
conv}{{{A}^{({2})}}}}$, let $a_{ik}$ and $a_{j\ell}$ be the neighboring
boundary vertices, and note that $U$ contains the two edges that connect
$a_{ij}$ to these vertices. Traverse the sequence of triangles $a_{i}uv$
incident to $a_{ij}$ and note that there is necessarily an edge, $uv$, such
that $u$ and $v$ neither share $i$ nor $j$ as a label. Hence, $a_{ij}uv$ is a
black triangle incident to $a_{ij}$. If there are two such black triangles,
then there is a white triangle between them. This white triangle is incident
to $a_{ij}$ but neither belongs to $W_{i}(U)$ nor to $W_{j}(U)$, which is not
possible.

Next let $\Delta=a_{ij}a_{ik}a_{jk}$ be any black triangle in $U$, and suppose
that the edge from $a_{i}$ to $a_{j}$ is not a side of ${{\rm conv}{A}}$. We
prove that there is exactly one other black triangle, $\Delta^{\prime}$, in
$U$ that shares $a_{ij}$, and that $\Delta$ and $\Delta^{\prime}$ lie on
opposite sides of the line that passes through $2a_{i}$ and $2a_{j}$. We
consider the case in which both $a_{i}$ and $a_{j}$ lie in the interior of
${{\rm conv}{A}}$. In all other cases, the argument is similar and omitted. In
the assumed case, $W_{i}(U)$ and $W_{j}(U)$ are both star-convex and meet at
$a_{ij}$. Traversing the triangles $a_{ij}uv$ incident to $a_{ij}$—starting at
$u=a_{ik}$ and ending at $v=a_{j\ell}$ while avoiding $\Delta$—we observe that
there must be a second black triangle, $\Delta^{\prime}$. Furthermore, there
cannot be three black triangles because $a_{ij}$ has only two labels and can
therefore not belong to three white regions. The property that $\Delta$ and
$\Delta^{\prime}$ lie on opposite sides of the line passing through $2a_{i}$
and $2a_{j}$ follows from the star-convexity of $W_{i}(U)$ and $W_{j}(U)$ and
the fact that these two regions touch at $a_{ij}$, which lies on this line and
between $a_{i}$ and $a_{j}$.

When we construct $F^{-1}(B(U))$, we get one white triangle next to every
boundary edge of ${{\rm conv}{A}}$ and two non-overlapping white triangles on
opposite sides of every non-boundary edge. A point in the interior of ${{\rm
conv}{A}}$ and sufficiently close to a boundary edge is covered by exactly one
triangle in $F^{-1}(B(U))$. To move to any other point in ${{\rm conv}{A}}$,
we walk from triangle to triangle, and each time we leave a triangle we enter
another. This implies that almost all points in ${{\rm conv}{A}}$ are covered
by exactly one triangle in $F^{-1}(B(U))$. It follows that $F^{-1}(B(U))$ is a
level-$1$ hypertriangulation of $A$. It is unique because the construction via
the inverse of the aging function is deterministic.

###  4.3 Flip-connectivity

We are now ready to prove the main result of this section. Given a generic set
$A\subseteq{{\mathbb{R}}}^{2}$, consider the graph whose nodes are the
level-$k$ hypertriangulations of $A$, with an arc connecting two nodes if
there is a flip that transforms one hypertriangulation to the other. We call
the level-$k$ hypertriangulations _flip-connected_ if this graph is connected.

######  Theorem 4.7.

For every generic point set $A\subseteq{{\mathbb{R}}}^{2}$, the level-$2$
hypertriangulations of $A$ are flip-connected.

######  Proof 4.8.

Let $U$ and $U^{\prime}$ be two level-$2$ hypertriangulations of $A$, and let
$T=F^{-1}(B(U))$ and $T^{\prime}=F^{-1}(B(U^{\prime}))$ be the corresponding
level-$1$ hypertriangulations, which are possibly partial triangulations of
$A$. If $T=T^{\prime}$, then $U$ and $U^{\prime}$ agree on their black
triangles. Similarly, the regions of white triangles are the same, but they
may be differently triangulated. Each such region is a convex or non-convex
polygon, and it is known that any two triangulations of a polygon are
connected by Type-I and Type-II flips; see [14].

So suppose $T\neq T^{\prime}$. It is also well known that possibly partial
triangulations of $A$ are connected by Type-I and Type-II flips; see Figure 5.
We will show that each Type-I flip on level $1$ corresponds to a Type-III flip
on level $2$, and each Type-II flip on level $1$ corresponds to a Type-IV flip
on level $2$. So we can perform the flips on the two levels in parallel, but
note that Type-I and Type-II flips on level $2$ are sometimes necessary to
enable the Type-III and Type-IV flips.

\begin{picture}(10149.0,2274.0)(664.0,-9523.0)\end{picture}

Figure 7: _Left:_ a Type-III flip on level $2$ superimposed on the
corresponding Type-I flip on level $1$. _Right:_ a Type-IV flip on level $2$
superimposed on the corresponding Type-II flip on level $1$.

In the case of a Type-I flip on level $1$, we need to retriangulate the white
regions on level $2$ as in Figure 7 on the left, so a Type-III flip can be
performed. Such a retriangulation with Type-I flips on level $2$ is always
possible. The case of a Type-II flip on level $1$ is similar, except that we
need Type-I as well as Tyle-II flips on level $2$ to retriangulate the three
white regions around the central black triangle to enable the Type-IV flip;
see Figure 7 on the right. Again, such a retriangulation is always possible.

We observe that mapping $a_{I}$ to $a_{[n]\setminus I}$ induces a bijection
between the level-$k$ and the level-$(n-k)$ hypertriangulations and their
respective flips. Hence, the flip-connectivity on level $1$ implies the flip-
connectivity on level $n-1$. More interestingly, Theorem 4.7 implies that also
the level-$(n-2)$ hypertriangulations of a generic set
$A\subseteq{{\mathbb{R}}}^{2}$ are flip-connected.

###  4.4 Obstacle for Generalization

To summarize, we used the aging function from level $1$ to level $2$ to prove
the flip-connectivity of level-$2$ hypertriangulations. It is not difficult to
generalize the aging function to higher levels, but Lemma 4.1 fails to
generalize, which is the reason the authors of this paper were not able to
prove flip-connectivity in full generality beyond level $2$. Indeed, it is
known that the extension of Lemma 4.1 to the aging function that maps white
triangles on level $2$ to black triangles on level $3$ fails already for five
points. In particular, the level-$2$ hypertriangulation in [22, Example 5.1]
contains three triangles, $\Delta_{1},\Delta_{2},\Delta_{3}$, whose images
under the aging function overlap; see Figure 8.

$1$$5$$2$$3$$4$$15$$12$$14$$24$$23$$34$$25$$125$$235$$124$$245$$145$$45$$345$$134$$234$$123$

Figure 8: _From left to right:_ a partial triangulation of five points with
two white triangles, a level-$2$ hypertriangulation with corresponding two
black triangles and six additional white triangles, and the corresponding six
aged black triangles, some of which overlap. The construction is based on
Example 5.1 by Olarte and Santos [22].

##  5 Flips beyond Level $2$

Because of the breakdown of Lemma 4.1 beyond level $2$, we restrict our
attention to special configurations for which the aging functions lemmas hold
even beyond level $2$. Most prominently, these are points in convex position
and coherent hypertriangulations. Before that, we review the more general
definition of flips in Baues posets and reformulate some results in our
language.

###  5.1 Baues Flips

We mention that all four types of flips studied in this paper are _geometric_
as they arise from geometric configurations of black and white triangles. An
alternative _combinatorial_ approach to flips originates from the Baues poset
of a fixed projection, $\pi\colon\Delta_{n}^{(k)}\to{A^{(k)}}$. It adopts the
combinatorial interpretation of $\Delta_{n}^{(k)}$ as a finite point set (with
implicit face structure), so that there is no need to take the convex hull of
${{A}^{({k})}}$ in the projection. We give a short description here and refer
to [28, 30] for details and a discussion of the flip-connectivity for general
Baues posets.

######  Definition 5.1.

The _Baues poset_ $\mathcal{B}(\Delta_{n}^{(k)}\to A^{(k)})$ of the projection
$\pi\colon\Delta_{n}^{(k)}\to{A^{(k)}}$ is the poset of hypersimplicial
subdivisions of $A^{(k)}$ ordered by refinement.

In this setting, the hypertriangulations are the rank-$0$ elements of the
Baues poset. The rank-$1$ elements are directly above the rank-$0$ elements,
and the _(combinatorial) flips_ are swaps between two rank-$0$ elements with
common rank-$1$ element right above them.

It is easy to see that flips of types I through IV defined in Section 3 are
flips in the Baues poset as well. Indeed, every such flip swaps one collection
of boundary triangles of a $3$-dimensional face of $\Delta_{n}^{(k)}$ for
another, while keeping the remaining triangles untouched. Using $\pi(F)$ and
all other triangles in the hypersimplicial subdivision gives a rank-$1$
element in the Baues poset. The converse inclusion of Baues flips into our
family of flips of types I through IV is not straightforward and may not hold
in general.

###  5.2 Points in Convex Position

If $A$ is in convex position, then the flip-connectivity of the family of
hypertriangulations using Baues flips was established by Postnikov [24, 25]
using the language of plabic graphs. More specifically, Postnikov introduced
plabic moves (M1)-(M3) and proved that these moves correspond to Baues flips
in the hypertriangulations, and that every two plabic graphs originating from
level-$k$ hypertriangulations of a set $A$ in convex position can be connected
by a sequence of plabic moves.

Combinatorially, moves (M1)-(M3) correspond to flips of Types I and III; see
Figure 9. Using Remark 3.2, we can see that every plabic move can be realized
as a (geometric) flip. This allows us to reformulate Postnikov’s result in our
language.

\begin{picture}(8404.0,1210.0)(2689.0,-4851.0)\end{picture}

Figure 9: _Left and middle:_ moves (M1) and (M2) in plabic graphs superimposed
on the corresponding Type-I flips applied to white and black triangles,
respectively. _Right:_ move (M3) in plabic graphs superimposed on the
corresponding Type-III flip in hypertriangulations.

######  Theorem 5.2 (Postnikov [25, Corollary 11.2]).

If $A\subseteq{{\mathbb{R}}}^{2}$ is a finite set of points in convex
position, then the family of level-$k$ hypertriangulations of $A$ is flip-
connected using flips of Types I and III.

Also, if $A$ is in convex position, then extensions of Lemmas 4.1 and 4.5 for
the aging function $F$ hold for every $k$; see [22, Section 6]. Here we
reformulate the result in our language and refer to [11, Corollary 4.4] and
[4, Lemma 3.6] for more details.

######  Theorem 5.3 (Galashin [11]).

Let $T$ be a level-$k$ hypertriangulation of a set
$A\subseteq{{\mathbb{R}}}^{2}$ of $n$ points in convex position. For $1\leq
k\leq n-1$, there exist possibly empty level-$(k-1)$ and level-$(k+1)$
hypertriangulations $S$ and $U$ of $A$ such that $B(U)=F(W(T))$ and
$B(T)=F(W(S)$.

This theorem can be used to get an alternative proof of Theorem 5.2 on flip-
connectivity of level-$k$ hypertriangulations for convex sets. Such an
alternative proof follows the ideas we used in Theorem 4.7. In the language of
plabic graphs this approach was implemented by Oh and Speyer [21].

###  5.3 Coherent Hypertriangulations

The flip-connectivity of the family of coherent hypertriangulations relates to
properties of the corresponding fiber polytope, $\mathcal{F}^{(k)}(A)$. In the
simplest case, for $k=1$, the edges of the secondary polytope,
$\mathcal{F}^{(1)}(A)$, correspond to bi-stellar flips, and in the generic
case, the flips between coherent triangulations result in edges of the
secondary polytope; see [6, Section 5.3], where coherent triangulations are
called regular.

As suggested in [25, Section 8], a similar property should hold for all Baues
posets (for generic projections) when we use Baues flips instead of bi-stellar
flips, but we did not find a precise statement to this effect in the
literature. We therefore include a short sketch of this property for
hypertriangulations using the more restrictive family of flips of Types I
through IV. We also refer to [6, Theorem 5.3.1] for a similar result on usual
triangulations (the case $k=1$), which inspired our proof.

######  Proposition 5.4.

If ${{\rm GKZ}{({T_{0}})}}$ and ${{\rm GKZ}{({T_{1}})}}$ are two vertices of
$\mathcal{F}^{(k)}(A)$ connected by an edge, then the coherent
hypertriangulations $T_{0}$ and $T_{1}$ differ by a flip of type I, II, III,
or IV (and thus also by a Baues flip).

######  Proof 5.5 (Sketch of proof.).

Let $T$ be the coherent subdivision that corresponds to the edge connecting
${{\rm GKZ}{({T_{0}})}}$ and ${{\rm GKZ}{({T_{1}})}}$. Since $T$ is not a
hypertriangulation, it contains the projection of a face, $F$, of dimension
$3$ or larger. If $\dim F\geq 4$, then $F$ is a hypersimplex, and the
corresponding coherent hypertriangulations give a fiber polytope of dimension
at least $2$ and hence cannot be the edge of $\mathcal{F}^{(k)}(A)$.

If $T$ contains projections of at least two faces $F$ and $F^{\prime}$ with
$\dim F=\dim F^{\prime}=3$, then lifting the points of $A^{(k)}$ according to
any height function, $h$, from the normal cone of the edge corresponding to
$T$ gives two non-triangular faces of the lower boundary of ${{\rm
conv}{A_{h}^{(k)}}}$. Each such face results in a linear equation for the
heights, $\\{h_{i}\\}_{i\in[n]}$, and since the edge has codimension $1$, the
equations for $F$ and $F^{\prime}$ must be proportional. This is possible only
if their lifting are parallel, which is impossible for the lower boundary of
${{\rm conv}{A_{h}^{(k)}}}$.

To summarize: the projection of $F$ is the only polygon where $T_{0}$ differs
from $T_{1}$, and since $\dim F=3$, this results in a flip from $T_{0}$ to
$T_{1}$.

Since all coherent level-$k$ hypertriangulations correspond to vertices of the
corresponding fiber polytope, the following corollary is immediate.

######  Corollary 5.6.

For every point set $A$, the family of all coherent level-$k$
hypertriangulations is flip-connected.

The converse property: that every flip between coherent hypertriangulations
corresponds to an edge of the fiber polytope, is worth considering as well. We
refer to [6, Theorem 5.3.3] for the treatment of triangulations of generic
point sets (the case $k=1$), and to [6, Example 5.3.4] for the non-generic
case. Below we prove the property for flips of Types III and IV.

######  Proposition 5.7.

If $T_{0}$ and $T_{1}$ are coherent level-$k$ hypertriangulations of $A$ that
differ by a flip of Type III or IV, then the vertices ${{\rm GKZ}{({T_{0}})}}$
and ${{\rm GKZ}{({T_{1}})}}$ of $\mathcal{F}^{(k)}(A)$ are connected by an
edge.

######  Proof 5.8 (Sketch of proof.).

Let $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$ be the sets of height functions
that induce coherent hypertriangulations $T_{0}$ and $T_{1}$, respectively.
These sets are full-dimensional convex cones.

Considering convex combinations of height functions from two different cones,
we get coherent subdivisions that coincide with $T_{0}$ and $T_{1}$ on all
common triangles. If the flip between $T_{0}$ and $T_{1}$ is of Type III or IV
(so it involves both black and white triangles), then one can show that the
edge between a black and a white triangle can disappear only if the change in
the coherent subdivision is a common coarsening of $T_{0}$ and $T_{1}$. Since
$T_{0}$ and $T_{1}$ differ only in the support of the flip, the two cones
intersect in a face of codimension $1$. This implies only one linear condition
on the heights. Thus, the common coarsening of $T_{1}$ and $T_{2}$ corresponds
to an edge of the fiber polytope.

For flips of Types I and II (which preserve the coloring of the manipulated
region), it is tempting to use the approach from [6, Theorem 5.3.3] and remove
the points that are not involved in the flip. However, it does not work in the
case of hypertriangulations as it could be impossible to remove the points
inside the quadrilateral or triangle where the flip happens without altering
the remaining coherent hypertriangulation. We thus conjecture that Proposition
5.7 does not extends to flips of Types I and II.

As the final remark on the topic, we notice that the aging function is also
applicable to coherent hypertriangulations.

######  Proposition 5.9.

Let $T$ be a coherent level-$k$ hypertriangulation of a finite set
$A\subseteq{{\mathbb{R}}}^{2}$. For $1\leq k\leq n-1$, there exist possibly
empty coherent level-$(k-1)$ and level-$(k+1)$ hypertriangulations $S$ and $U$
of $A$ such that $B(U)=F(W(T))$ and $B(T)=F(W(S))$.

######  Proof 5.10.

We can use the height function that generates $T$ to also construct $S$ and
$U$.

##  6 Concluding Remarks

This section mentions avenues for further research on hypertriangulations and
their flips. In dimension $d=2$, there is of course the open question of flip-
connectivity for levels $k$ between $3$ and $n-3$, in which $n$ is the number
of points.

Beyond 2 dimensions. In dimension $d\geq 3$, the question of flip-connectivity
for hypertriangulations has yet to be formalized. Even for generic sets of $n$
points, hypertriangulations beyond level $1$ are generally not simplicial
because generic hypersimplices are not necessarily simplices. The aging
function can still be defined and goes through $d$ generations of a
$d$-simplex: for $1\leq j\leq d-1$ from the convex hull of the barycenters of
the $(j-1)$-faces to the convex hull of the barycenters of the $j$-faces. For
example in dimension $d=3$, it goes from a tetrahedron (convex hull of its
vertices) to an octahedron (convex hull of the midpoints of its edges) to
another tetrahedron (convex hull of the barycenters of its triangles). Flips
would be defined as in Section 3, which is best described in terms of
projections from $d+1$ dimensions. According to Radon’s theorem, there are
$d+1$ combinatorially different projections of a $(d+1)$-simplex to
${{\mathbb{R}}}^{d}$ [26]. The types are paired up, giving
${\left\lceil(d+1)/2\right\rceil}$ flips. The $(d+1)$-simplex has $d+1$
generations, but there is a symmetry between the barycenters of the
$(j-1)$-faces and the $(d+1-j)$-faces, giving
${\left\lceil(d+1)/2\right\rceil}$ cases. We thus get
${\left\lceil(d+1)/2\right\rceil}^{2}$ flips, namely four in
${{\mathbb{R}}}^{2}$, also only four in ${{\mathbb{R}}}^{3}$, but nine in
${{\mathbb{R}}}^{4}$.

Moves in plabic graphs. Section 5.2 relates flips of Types I and III to moves
(M1)-(M3) in plabic graphs, as introduced by Postnikov [24]. The other two
types of flips can be used to create additional moves in plabic graphs as
every hypertriangulation has an underlying trivalent plabic graphs with black
and white vertices. Notably, moves (M1)-(M3) keep the reducibility of plabic
graphs and preserve the strand permutation, while the moves defined using
flips of Types II and IV do not have these invariants; see [4, 24] for precise
definitions of the notions related to plabic graphs.

It is unclear whether the two additional moves can be used to reduce every
plabic graph, or at least every plabic graph originating from a
hypertriangulation. Indeed, this question is related to the flip-connectivity
of hypertriangulations, as for every finite $A$ and level $k$, there exists a
level-$k$ hypertriangulation of $A$ that results in a reduced plabic graph.
This fact can be proved by an induction on $n=|A|$, removing a point on the
boundary of the convex hull of $A$ and adding it back while tracking how the
convex hull of $A^{(k)}$ changes. It is also conceivable that the higher-
dimensional flips described earlier are related to higher-dimensional plabic
graphs and associated moves, as described in [12].

Generalized Baues problem. One of the main questions in the theory of induced
subdivisions is the _generalized Baues problem_. Roughly, the question asks
how well the family of all induced subdivisions embeds the family of coherent
subdivisions. A more specific question asks whether the order complex of the
poset of all induced subdivisions is homotopy equivalent to the order complex
of the poset of coherent subdivisions. We refer to the survey of Reiner [28]
for precise definitions and details.

In the setting of ($2$-dimensional) hypertriangulations, the generalized Baues
problem has a positive answer for $k=1$, the case of usual triangulations, as
shown by Edelman and Reiner [8]. Consequently, the problem has also a positive
answer for $k=n-1$. In addition, Olarte and Santos [22] proved that the
generalized Baues problem has a positive answer if the points are in convex
position. For an arbitrary generic set in ${{\mathbb{R}}}^{2}$, the
generalized Baues question for level-$k$ hypertriangulations remains open for
all $2\leq k\leq n-2$.

#### Acknowledgements

The second author thanks Jesús A. De Loera for useful discussions on flips and
non-flips.

## References

  * [1]
  * [2] C. Athanasiadis. Projections of polytopes on the plane and the generalized Baues problem. _Trans. Am. Math. Soc._ 129:7 (2001), 2103–2109.
  * [3] F. Aurenhammer. A new duality result concerning Voronoi diagrams. _Discrete Comput. Geom._ 5 (1990), 243–-254.
  * [4] A. Balitskiy and J. Wellman Flip cycles in plabic graphs. _Sel. Math. New Ser._ 26 (2020), 15.
  * [5] L.J. Billera and B. Sturmfels. Fiber polytopes. _Ann. Math._ 135 (1992), 527–549.
  * [6] J.A. De Loera, J. Rambau and F. Santos _Triangulations. Structures for Algorithms and Applications._ Springer-Verlag, Berlin, 2010.
  * [7] P.H. Edelman and V. Reiner. Catalan triangulations of the Möbius band. _Graphs Combin._ 13 (1997), 231–243, https://doi.org/10.1007/BF03353000.
  * [8] P.H. Edelman and V. Reiner. Visibility complexes and the Baues Problem for triangulations in the plane. _Discrete Comput. Geom._ 20 (1998), 35–59, https://doi.org/10.1007/PL00009377.
  * [9] H. Edelsbrunner and G. Osang. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. _Algorithmica_ (2022), https://doi.org/10.1007/s00453-022-01027-6.
  * [10] H. Edelsbrunner and N.R. Shah. Incremental topological flipping works for regular triangulations. _Algorithmica_ 15 (1996), 223–241, https://doi.org/10.1007/BF01975867.
  * [11] P. Galashin. Plabic graphs and zonotopal tilings. _Proc. London Math. Soc._ 117:4 (2018), 661–681.
  * [12] P. Galashin, T. Lam, M. Shermann-Bennett and D. Speyer. Braid variety cluster structures, I: 3D plabic graphs. Preprint, 2022, https://arxiv.org/abs/2210.04778.
  * [13] I.M. Gelfand, M.M. Kapranov and A.V. Zelevinsky. _Discriminants, Resultants and Multidimensional Determinants._ Birkhäuser, Boston, Massachusetts, 1994.
  * [14] F. Hurtado, M. Noy and J. Urrutia. Flipping edges in triangulations, _Discrete Comput. Geom._ 22 (1999), 333–346.
  * [15] B. Joe. Three-dimensional triangulations from local transformations. _SIAM J. Sci. Stat. Comput._ 10 (1989), 718–741.
  * [16] B. Joe. Construction of three-dimensional Delaunay triangulations using local transformations. _Comput. Aided Geom. Design_ 8 (1991), 123–142.
  * [17] C.L. Lawson. Software for $C^{1}$ Surface Interpolation. In _Mathematical Software_ , Proc. Sympos. at the Mathematics Research Center, Univ. Wisconsin–Madison, March 28–30, 1977, pages 161–194.
  * [18] G. Liu. A zonotope and a product of two simplices with disconnected flip graphs. _Discrete Comput. Geom._ 59 (2018), 810–842. https://doi.org/10.1007/s00454-018-9971-6.
  * [19] G. Liu. Flip-connectivity of triangulations of the product of a tetrahedron and simplex. _Discrete Comput. Geom._ 63 (2020), 1–30, https://doi.org/10.1007/s00454-019-00157-z.
  * [20] G. Liu. A counterexample to the extension space conjecture for realizable oriented matroids. _Proc. London Math. Soc._ 101:1 (2020), 175–193, https://doi.org/10.1112/jlms.12264.
  * [21] S.H. Oh and D.E. Speyer. Links in the complex of weakly separated collections. _J. Comb._ 8:4 (2017), 581–592.
  * [22] J.A. Olarte and F. Santos. Hypersimplicial subdivisions. _Sel. Math. New Ser._ 28 (2021), 4.
  * [23] I. Pak. History of Catalan numbers. Preprint (2014), https://arxiv.org/abs/1408.5711.
  * [24] A. Postnikov. Total positivity, Grassmannians, and networks. ArXiv preprint (2006), https://arxiv.org/abs/math/0609764v1.
  * [25] A. Postnikov. Positive Grassmanian and polyhedral subdivisions. In _Proceeding of International Congress of Mathematicians_ , Rio de Janeiro (2018), 3199–3230.
  * [26] J. Radon. Mengen konvexer Körper, die einen gemeinsame Punkt enthalten. _Math. Ann._ 83 (1921), 13–15.
  * [27] J. Rambau, G. Ziegler. Projections of polytopes and the generalized baues conjecture. _Discrete Comput. Geom._ 16 (1996), 215–237, https://doi.org/10.1007/BF02711510.
  * [28] V. Reiner. The generalized Baues problem. In _New Perspectives in Algebraic Combinatorics_ , Math. Sci. Res. Inst. Publ. 38 (1999), 293–336.
  * [29] F. Santos. A point set whose space of triangulations is disconnected. _J. Amer. Math. Soc._ 13:3 (2000), 611–637, http://www.jstor.org/stable/2646121.
  * [30] F. Santos. On the refinements of a polyhedral subdivision. _Collect. Math._ 52:3 (2001), 231–256, http://dmle.icmat.es/pdf/COLLECTANEAMATHEMATICA_2001_52_03_03.pdf.
  * [31] F. Santos. The Cayley trick and triangulations of products of simplices. In _Integer Points in Polyhedra - Geometry, Number Theory, Algebra, Optimization_ , A. Barvinok, M. Beck, C. Haase, B. Reznick, and V. Welker (eds), Contemporary Mathematics 374 (2005).
  * [32] R. Sibson. Locally equiangular triangulations. _Comput. J._ 21 (1978), 243–245.
  * [33] K. Wagner. Bemerkungem zum Vierfarbenproblem, Jber. Deutsch. Math-Verein. 46 (1936), 26–32.
  * [34] U. Wagner and E. Welzl. Connectivity of triangulation flip graphs in the plane. _Discrete Comput. Geom._ (2022), https://doi.org/10.1007/s00454-022-00436-2.
  * [35] G.M. Ziegler. _Lectures on Polytopes._ Springer-Verlag, New York, 2008.


# WB LUTs: Contrastive Learning for White Balancing Lookup Tables

###### Abstract

Automatic white balancing (AWB), one of the first steps in an integrated
signal processing (ISP) pipeline, aims to correct the color cast induced by
the scene illuminant. An incorrect white balance (WB) setting or AWB failure
can lead to an undesired blue or red tint in the rendered sRGB image. To
address this, recent methods pose the post-capture WB correction problem as an
image-to-image translation task and train deep neural networks to learn the
necessary color adjustments at a lower resolution. These low resolution
outputs are post-processed to generate high resolution WB corrected images,
forming a bottleneck in the end-to-end run time. In this paper we present a 3D
Lookup Table (LUT) based WB correction model called WB LUTs that can generate
high resolution outputs in real time. We introduce a contrastive learning
framework with a novel hard sample mining strategy, which improves the WB
correction quality of baseline 3D LUTs by $25.5\%$. Experimental results
demonstrate that the proposed WB LUTs perform competitively against state-of-
the-art models on two benchmark datasets while being $300\times$ faster using
$12.7\times$ less memory. Our model and code are available at
https://github.com/skrmanne/3DLUT_sRGB_WB111The authors acknowledge Bruce
Maxwell for helpful discussions during the problem formulation..

Index Terms—  White Balance Correction, 3D LUT, Contrastive Learning, Hard
Sample Mining.

##  1 Introduction

Human visual perception adaptively discerns scene colors as constant, even
under different lighting conditions. Since cameras do not inherently perform
this adaptation, a color balancing process is needed to transform a captured
image to conform with viewer expectations. Automatic white balancing (AWB) is
an important aspect of any integrated signal processing (ISP) pipeline that
renders images with perceptually true object colors. However, when WB settings
are inaccurate, images are rendered with undesired color tints. Conventional
color constancy methods [1, 2], which are based on a linear relationship
between illuminant color and image intensity in the linear domain, are
ineffective for post-capture white balance correction due to the non-linear
operations performed in the ISP to render an sRGB image. To this end, several
approaches have been proposed for WB correction based on $k$-nearest neighbors
(KNN) clustering, image-to-image translation, and polynomial fitting. These
models often operate on downsampled inputs to avoid computationally expensive
full resolution processing. Subsequent post-processing steps, such as edge-
aware upsampling [3] and color mapping [4] are employed to generate high
resolution images. While these models demonstrate efficiency with low
resolution inputs, the need for post-processing creates a bottleneck for real
time processing, as illustrated in Fig. 1.

Fig. 1: Comparison of performance and WB correction quality of our method with
the state-of-the-art, on the Rendered Cube dataset [5]. Performance is gauged
both by the run time, on the vertical axis, and the model memory, which is
proportional to the size of the marker for each model.

By contrast, certain imaging processing pipelines use efficient 3D lookup
tables (3D LUTs) to apply various finishing styles directly on the high
resolution images with high efficiency. However, traditional 3D LUTs are
manually tuned for each rendering style and lack generalizability. More
recently, researchers have proposed methods to adaptively learn 3D LUTs for
image retouching, achieving state-of-the-art quality with real time
performance. Zeng et al. [6] propose to use a set of basis LUTs and a scene
classifier to adaptively regulate each LUT’s contribution to an image,
creating scene-adaptive LUTs for image editing. However, unlike the image
retouching task, WB correction requires different levels of color correction
based on the scene and the illuminant. Hence, 3D LUTs without any direct
supervision for the scene classifier struggle to generate rich illumination-
oriented representations from the image.

Khosla et al. [7] proposed a supervised contrastive loss to learn
representations that cluster together for similar images while pushing
representations from dissimilar images farther. Motivated by the success of
contrastive learning in other low-level vision tasks [2], we propose a
contrastive learning scheme for LUTs with a novel hard sample mining strategy.
The proposed contrastive learning framework encourages the model to learn
illumination-oriented, scene-agnostic representations, thereby improving the
WB correction efficacy. Our key contributions are as follows:

  * •

We propose WB LUTs for sRGB white balance correction as an alternative to
image-to-image translation models. To the best of our knowledge, we are the
first to use LUTs for white balance correction.

  * •

We introduce a contrastive learning framework for LUTs with a novel hard
sample mining strategy to learn scene-agnostic features and show $25.5\%$
improvement over baseline 3D LUTs.

  * •

We achieve near state-of-the-art quality on WB correction with $300\times$
speed and $12.7\times$ smaller memory usage compared to current models.

##  2 Related Work

###  2.1 WB Correction for sRGB Images

Post-capture white balance correction was first proposed by Afifi et al. [8]
along with a dataset of 65,000 images rendered with incorrect WB setting and
corresponding ground truth images. For a given image, a $k$-nearest neighbours
(KNN) based approach estimates a color mapping function to correct the color
cast in the image. Following this work, Afifi and Brown [4] propose a deep
neural network to estimate a white balanced image along with two auxiliary
outputs at tungsten and shade WB settings corresponding to 2800 K and 7500 K
color temperatures respectively. The additional color temperature temperatures
allow users to create images with different WB appearance through weighted
fusion. In MixedWB [3], the authors improve the model’s capability to handle
mixed illumination settings for white balancing. By improving the ISP
pipeline, they generate images at different fixed color temperatures. These
images are then fed to a convolutional neural network (CNN) to estimate soft
weighing masks for the weighted fusion of images at different color
temperatures. The low resolution masks are upsampled using a bilateral solver
to create the output at full resolution. More recently, Li et al. [9] address
the instability issue of current models and propose a stable WB model that
relies on low-frequency color temperature-insensitive features to generate
consistent outputs for different WB settings. Li et al. [10] improve the
generalizability of their WB correction model using a few-shot model to learn
camera-aligned pseudo raw features, reducing the errors for images from camera
models not seen during the training.

###  2.2 3D Lookup Tables (3D LUTs)

Lookup tables are often used in image editing to render images with different
finishing styles and are manually tuned for a specific preset style. Zeng et
al. [6] propose image adaptive 3D LUTs for the task of image retouching and
demonstrate superior quality with real time inference speeds for high
resolution (4K) images. Subsequent work [11, 12] builds upon this initial
research, enhancing the aesthetic quality of images through increased network
complexity. LUTs are rapidly being adapted to various computer vision tasks
such as super resolution [13], segmentation [14], image fusion [15], network
quantization [16] etc. Motivated by the generalizability to several tasks,
superior quality, and fast inference in image retouching, we propose a LUT-
based approach for sRGB white balance correction.

##  3 Proposed Method

###  3.1 Revisiting 3D LUTs

A 3D LUT is a convenient way to describe global functions for image
processing. By definition, a 3D LUT is described by a 3-dimensional array
$\phi$ with size $(M,M,M)$, visualized as a 3D cubic lattice. In our paper, we
work with 8-bit images with corresponding color channels of 256 dimensions,
and set $M=33$. For a pixel $(x,y,z)$ with intensities that each happen to be
divisible by 8, the 3D LUT can be applied as a transformation $\Phi$ to
$(x,y,z)$ simply by “looking up” the value of the scaled index in the array
$\phi$:

$\Phi(x,y,z):=\phi_{(x/8,y/8,z/8)}$

For the general (non-divisible) pixel $(x,y,z)$, the value of $\Phi(x,y,z)$ is
determined by trilinear interpolation of $\phi$ over the eight nearest
integral divisible vertices. The 3D LUT $\phi$ can be applied to an image by
applying it to each pixel uniformly. In practice, this construction
encapsulates a wide range of global transformations—which are continuous with
respect to pixel intensity and can be applied quickly—in a relatively small
function space ($33^{3}=35,937$ dimensions).

Zeng et al. [6] proposed adaptive 3D LUTs learned from large datasets for
image enhancement. A scene classifier network and $N$ basis LUTs are trained
collectively to learn image-adaptive LUTs. The classifier weights are used to
fuse the basis LUTs into a single image-adaptive LUT for a given image as
follows:

$\phi=\sum_{n=1}^{N}w_{n}\phi^{n}$ (1)

where $\phi^{1..n}$ are the basis LUTs, $w_{1..n}$ are the estimated weights
from the classifier, and $\phi$ is the fused LUT.

This method of training LUTs and the classifier benefits from optimal
collaboration between both the image and LUT features and results in a
lightweight model for image editing. Since LUTs are resolution agnostic,
training and inference can be done on a downsampled image to retrieve an
adaptive LUT for the task, see Fig. 2. This adaptive LUT can be used to
generate a high resolution output without loss in quality for global image
retouching tasks. Since white balancing is a global color correction problem,
3D LUTs offer an attractive alternative to traditional image-to-image
translation CNNs.

Fig. 2: Downsampled input $I_{\downarrow}$ is fed to the scene classifier to
generate weights for basis LUT fusion. The adaptive LUT is used to correct the
high resolution image.

###  3.2 Contrastive learning for WB LUTs

Following 3D LUTs [6], we use a scene classifier network to produce scene
adaptive weights for the basis LUTs. Initial tests showed this approach to be
very effective overall, but images with extreme starting color temperatures
yielded images with residual color tints. We hypothesize that the lack of
direct supervision for the scene classifier, resulting in scene-oriented
features, is the primary cause for the degradation. In a similar task of color
constancy, contrastive learning has shown significant improvements over the
baseline model by generating rich illumination-oriented representations [2].
Hence, we utilize contrastive learning as supervision for the scene classifier
to learn rich illumination-oriented, scene-agnostic representations.
Contrastive learning typically proceeds by comparing an anchor sample to a
similar positive sample and a dissimilar negative sample, with the desired
contraction or separation enforced by a special loss function. In the context
of white balance correction, images that require similar WB correction are
considered similar even when the underlying scene is different, and
conversely, images of the same scene are considered dissimilar if the WB
correction required is different.

The effectiveness of contrastive learning hinges on challenging samples that
are harder to distinguish. Hence, Lo et al. [2] propose data augmentation
techniques to create hard positive and hard negative samples. These samples
are generated by creating images with same scene content and different
illuminants, as well as different scene content with same illuminants.
However, such data augmentation is not possible in the post-capture WB
correction task due to the lack of ground truth illumination information and
raw images. Instead, we use the ground truth sRGB images to create hard
negative and hard positive samples, as detailed below.

Fig. 3: Two images, both rendered with the Cloudy WB setting, illustrate how
the same white balance rendering can result in different color mappings for
different scenes.

####  3.2.1 Hard negative samples

Datasets for sRGB white balance correction include input images rendered with
incorrect WB settings, white-balanced ground truth images, and auxiliary
images captured at different camera color temperature settings. Specifically,
in the Rendered WB dataset Set1 [8] each scene includes a rendering under the
correct WB setting (serving as the ground truth), as well as additional images
rendered under the following WB settings from the camera: Tungsten (2850 K),
Fluorescent (3800 K), Daylight (5500 K), Cloudy (6500 K), and Shade (7500 K).
While training, these additional renderings can be used as hard negative
samples $I^{N}_{A}$ for a given input, $I_{A}$.

Fig. 4: Overview of proposed contrastive learning approach for LUTs. For an
image $I_{A}$ and its ground truth $I^{\text{gt}}_{A}$, we select an image of
the same scene rendered with a different color temperature as negative sample
$I^{N}_{A}$. Ground truth image of a different scene $I^{\text{gt}}_{B}$ is
color mapped to generate a hard positive sample
$I^{P}_{A}:=M^{\star}\psi(I^{\text{gt}}_{B})$. These hard positive and
negative samples are used in the contrastive learning framework supervised
with triplet loss.

####  3.2.2 Hard positive samples

A straightforward approach to generate positive samples is geometric
augmentations such as random crop or flipping, but these will feature the same
underlying scene, creating easily distinguishable samples. In order to
encourage the network to learn stronger scene-independent representations, it
is essential to generate hard positive samples with different scene content,
but with the same WB correction required as the anchor image. Another approach
to create positive samples could involve utilizing images from different
scenes rendered using the same camera WB setting as the anchor image. However,
this approach may not always yield similar samples, as images rendered with
the same WB settings might still require different levels of WB correction, as
shown in Fig. 3.

These considerations lead us to the following color transformation technique
for generating hard positive samples: given an anchor image $I_{A}$, its
ground truth $I^{\text{gt}}_{A}$, along with a separate ground truth image
$I^{\text{gt}}_{B}$ representing a different scene, we determine a coarse
approximation of the WB correction needed to transform $I_{A}$ into the ground
truth $I^{\text{gt}}_{A}$, and apply the inverse of that transformation to
$I^{\text{gt}}_{B}$ to obtain the hard positive sample. The generated hard
positive sample then needs approximately the same WB correction as $I_{A}$.
This approximation is mediated via the degree 2 polynomial transformation map
$\psi:\mathbb{R}^{3}\to\mathbb{R}^{11}$ defined by
$(r,g,b)\mapsto(r,g,b,rg,rb,gb,r^{2},b^{2},g^{2},rgb,1)$ [8]. Specifically,
given $I^{\text{gt}}_{A}$, we find a $11\times 3$ color correction $M^{\star}$
satisfying the optimization

$M^{\star}:=\arg\min_{M}\left\|I_{a}-M\psi(I^{\text{gt}}_{A})\right\|_{2}$ (2)

representing the inverse of the optimal transformation taking $I_{A}$ to
$I^{\text{gt}}_{A}$. Then, given a second ground truth image
$I^{\text{gt}}_{B}$, we define the positive sample by
$I^{P}_{A}:=M^{\star}\psi(I^{\text{gt}}_{B})$.

###  3.3 Architecture details

Our model has four components, as illustrated in Fig. 4: a scene classifier, a
multi-layer perceptron (MLP), a weight generator, and the LUTs. The scene
classifier is composed of 5 convolution layers, each with stride 2 and kernel
size 3. The MLP is only used during training to generate anchor, positive, and
negative features for contrastive learning. It consists of two linear layers
and generates a 128-dimensional feature for each sample. The weight generator,
composed of 2 convolution layers, generates $N$ weights corresponding to $N$
basis LUTs.

| $\Delta\text{E}2000(\downarrow)$ | MAE ($\downarrow$) | Time | Params | Size
---|---|---|---|---|---
Method | Mean | Q1 | Q2 | Q3 | Mean | Q1 | Q2 | Q3 | (ms) | (K) | (MB)
Rendered WB dataset Set2
KNNWB [8] | 5.60 | 3.43 | 4.90 | 7.06 | 4.48∘ | 2.26∘ | 3.64∘ | 5.95∘ | 820 | 6108 | 21.8
MixedWB [3] | 6.05 | 3.45 | 4.92 | 7.20 | 4.92∘ | 2.69∘ | 4.10∘ | 6.37∘ | 1550 | 1313 | 5.09
DeepWB [4] | 4.90 | 3.13 | 4.35 | 6.08 | 3.75∘ | 2.02∘ | 3.08∘ | 4.72∘ | 1090 | 4366 | 16.7
WBFlow [9] | 4.64 | 3.16 | 4.07 | 5.56 | 3.51∘ | 1.93∘ | 2.92 | 4.47∘ | 1080 | 7570 | 30.6
WB LUTs (Ours) | 4.71 | 3.26 | 4.17 | 5.47 | 3.31∘ | 1.95∘ | 2.77∘ | 4.23∘ | 3.7 | 593 | 2.40
Rendered Cube dataset
KNNWB [8] | 5.68 | 3.22 | 4.61 | 6.70 | 4.12∘ | 1.96∘ | 3.17∘ | 5.04∘ | 810 | 6108 | 21.8
MixedWB [3] | 5.03 | 2.07 | 3.12 | 7.19 | 4.20∘ | 1.39∘ | 2.18∘ | 5.54∘ | 1520 | 1313 | 5.09
DeepWB [4] | 4.59 | 2.68 | 3.81 | 5.53 | 3.45∘ | 1.87∘ | 2.82∘ | 4.26∘ | 1080 | 4366 | 16.7
WBFlow [9] | 4.28 | 2.71 | 3.77 | 5.21 | 3.34∘ | 1.94∘ | 2.82∘ | 4.11∘ | 1070 | 7570 | 30.6
WB LUTs (Ours) | 4.33 | 2.84 | 3.71 | 5.02 | 3.28∘ | 1.88∘ | 2.62∘ | 3.91∘ | 3.7 | 593 | 2.40

Table 1: Quantitative comparison of our method against state-of-the-art WB
correction models on Rendered WB dataset Set2 [8] and Rendered Cube dataset
[5]. Best results in each category are in bold and second-best results are
underlined.

###  3.4 Loss Functions

Our loss function combines a standard direct supervision loss measuring pixel-
wise error, and a contrastive loss between the anchor $f_{A}$, positive
$f_{P}$, and negative features $f_{N}$ from the MLP. Given a batch of $B$
images $\left(I_{A_{i}}\right)_{i=1}^{B}$, the direct supervision loss is
given by

$L_{\text{WB}}=\dfrac{1}{B}\sum_{i=1}^{B}\left\|I^{\text{out}}_{A_{i}}-I^{\text{gt}}_{A_{i}}\right\|_{2},$
(3)

where $I^{\text{gt}}_{A_{i}}$ is the ground truth image for $I_{A_{i}}$. The
triplet loss involves, for each anchor feature $f_{A_{i}}$, the corresponding
hard positive feature $f^{P}_{A_{i}}$ and hard negative feature
$f^{N}_{A_{i}}$, obtained from corresponding samples as described in Section
3.2:

$L_{\text{tri}}=\dfrac{1}{B}\sum_{i=1}^{B}\left\|f_{A_{i}}-f^{P}_{A_{i}}\right\|_{2}-\left\|f_{A_{i}}-f^{N}_{A_{i}}\right\|_{2}.$
(4)

Fig. 5: Results from base 3D LUTs vs WB LUTs, trained with the proposed
contrastive learning framework, with $\Delta E2000$ for each output overlaid
onto the image.

We also retain two regularization terms used in [6]: the smooth regularization
loss $L_{\text{s}}$, which encourages smoothness in the values of each 3D LUT
across neighbouring indices; and the monotonicity loss $L_{\text{m}}$, which
encourages values of the 3D LUT to increase as the indices increase.

All together, the model is trained with the following weighted combination of
the above loss functions:

$L=\lambda_{\text{WB}}L_{\text{WB}}+\lambda_{\text{tri}}L_{\text{tri}}+\lambda_{\text{s}}L_{\text{s}}+\lambda_{\text{m}}L_{\text{m}}.$
(5)

We choose the following weights empirically: $\lambda_{\text{WB}}=1.0$,
$\lambda_{\text{s}}=0.0001$, and $\lambda_{\text{m}}=10.0$. For the
contrastive loss weight, we set $\lambda_{\text{tri}}=10.0$ for the first 100
epochs and then reduce the effect with $\lambda_{\text{tri}}=1.0$ for the
remainder.

##  4 Experiments

###  4.1 Implementation details

Following prior work [4, 3, 10], we use 12,000 images from Rendered WB dataset
Set1 for training the model. We used Rendered WB dataset Set2 [8] and Rendered
Cube [5] datasets for our evaluation. Our model, implemented in PyTorch with
CUDA, is trained using the Adam optimizer with $\beta_{1}=0.9$ and an initial
learning rate set to $0.0001$. Training is done on randomly cropped patches of
$256\times 256$ with random horizontal and vertical flipping. We set batch
size as 32 and train all models for 200 epochs. During testing, a downsampled
image of size $256\times 256$ is used to generate the adaptive LUT, and the
look up operation is performed on the high resolution image to achieve real
time WB correction. Similar to WBFlow [10], we report the mean, first (Q1),
second (Q2), and third (Q3) quantile of mean angular error (MAE) and the
International Commission on Illumination (CIE) $\Delta\text{E}2000$ measure
for color accuracy [17].

|  $\Delta\text{E}2000$ ($\downarrow$)
---|---
Model | Mean | Q1 | Q2 | Q3
3D LUTs [6] | 4.39 | 2.67 | 3.74 | 5.57
3D LUTs + Easy positive | 4.04 | 2.13 | 3.41 | 5.22
3D LUTs + Hard positive | 3.68 | 1.67 | 2.82 | 4.84
3D LUTs + LAB | 4.06 | 1.87 | 3.40 | 5.08
WB LUTs (Ours) | 3.27 | 1.13 | 2.43 | 4.43
Table 2: Ablation study comparing base 3D LUTs trained with the different
contrastive learning strategies and color spaces, evaluated on Rendered WB
Set1 validation split. Fig. 6: Qualitative comparison of our method against
KNNWB [8], DeepWB [4], and MixedWB [3] on images from Rendered WB Set2 [8] and
Rendered Cube [5] datasets.

###  4.2 Ablation study

To illustrate the benefits of the proposed contrastive learning scheme and the
novel hard positive mining strategy, we validate various models on Rendered WB
Set1 validation split. Along with RGB color space, we train 3D LUTs in color
spaces that separate brightness and color components to emphasize color
correction and find that LAB color space performs best. These results are
presented in Table 2. Training with hard positive samples improves mean
$\Delta E2000$ by 16%, compared to 8% improvement using easy positive samples.
Hence, we train WB LUTs in LAB color space with hard positive samples. Effects
of color temperature on the outputs can be seen in Fig. 5, residual blue tint
remains in outputs from 3D LUTs, while WB LUTs maintain lower
$\Delta\text{E}2000$ across different color temperatures, showing consistent
WB correction across color temperatures.

###  4.3 Performance

Performance of WB LUTs is compared against current state-of-the-art methods in
Table 1. WB LUTs are $300\times$ faster compared to WBFlow and require
$12.7\times$ less memory, and fewer parameters compared to any current model.
We measure the average run time of all the models on two datasets and include
any pre/post-processing necessary to generate outputs at full resolution.

###  4.4 Results

We compare our method against KNNWB [8], DeepWB [4], MixedWB [3], and WBFlow
[10]. Each of these methods estimates a lower resolution WB corrected image
and uses different post-processing methods like polynomial fitting or
bilateral upsampling to generate a high resolution image.

Table 1 presents performance results of the aforementioned models under MAE
and $\Delta E2000$ metrics, on Rendered WB dataset Set2 and the Rendered Cube
datasets. Both of these datasets include images taken with different cameras
from the training dataset, making them robust tests for generalizability. The
results show our model performing competitively against WBFlow under both
metrics. Notably, our model shows strong Q2 and Q3 performance, suggesting our
contrastive approach succeeds in reigning in poor performance on more extreme
input images.

Fig. 6 illustrates the effectiveness our method against WB correction from
KNNWB [8], DeepWB [4], and MixedWB [3] models. Our results show comparative WB
correction without any artifacts in high resolution outputs generated using
available code and their pretrained models. We also see relatively smoother WB
correction without large differences in the image colors compared to the
ground truth, see KNNWB output in the top row, flowers are colored differently
than other methods and the ground truth. Our model consistently generates WB-
corrected images of higher quality compared to other models, particularly for
images with extreme color temperatures, closely followed by DeepWB, as
indicated by the overlaid $\Delta E2000$ values on the images.

##  5 Future work & Conclusion

We present WB LUTs, a LUT-based approach for white balance correction
improving the quality of baseline 3D LUTs using contrastive learning with hard
sample mining. Our model, WB LUTs, achieves near state-of-the-art WB
correction on two datasets while generating high resolution images with high
efficiency. Although color correction is usually a global image manipulation
task, our approach can not handle the cases where a scene is illuminated by
two or more illuminants. Future work could include an efficient post-
processing step for local color cast correction from different illuminants
similar to local contrast enhancement from [6].

## References

  * [1] Jonathan T. Barron,  “Convolutional color constancy,”  in 2015 IEEE International Conference on Computer Vision (ICCV), Santiago, Chile, Dec. 2015, p. 379–387, IEEE.
  * [2] Yi-Chen Lo, Chia-Che Chang, Hsuan-Chao Chiu, Yu-Hao Huang, Chia-Ping Chen, Yu-Lin Chang, and Kevin Jou,  “Clcc: Contrastive learning for color constancy,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 8053–8063.
  * [3] Mahmoud Afifi, Marcus A. Brubaker, and Michael S. Brown,  “Auto white-balance correction for mixed-illuminant scenes,”  in 2022 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), Waikoloa, HI, USA, Jan. 2022, p. 934–943, IEEE.
  * [4] Mahmoud Afifi and Michael S. Brown,  “Deep white-balance editing,”  in 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Seattle, WA, USA, June 2020, p. 1394–1403, IEEE.
  * [5] Nikola Banić, Karlo Koščević, and Sven Lončarić,  “Unsupervised learning for color constancy,”  arXiv preprint arXiv:1712.00436, 2017.
  * [6] Hui Zeng, Jianrui Cai, Lida Li, Zisheng Cao, and Lei Zhang,  “Learning image-adaptive 3d lookup tables for high performance photo enhancement in real-time,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 4, pp. 2058–2073, 2020.
  * [7] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan,  “Supervised contrastive learning,”  Advances in neural information processing systems, vol. 33, pp. 18661–18673, 2020.
  * [8] Mahmoud Afifi, Brian Price, Scott Cohen, and Michael S. Brown,  “When color constancy goes wrong: Correcting improperly white-balanced images,”  in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Long Beach, CA, USA, June 2019, p. 1535–1544, IEEE.
  * [9] Chunxiao Li, Xuejing Kang, Zhifeng Zhang, and Anlong Ming,  “Swbnet: A stable white balance network for srgb images,”  Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 11, pp. 1278–1286, June 2023.
  * [10] Chunxiao Li, Xuejing Kang, and Anlong Ming,  “Wbflow: Few-shot white balance for srgb images via reversible neural flows,”  in Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023, pp. 1026–1034.
  * [11] Xiang Zhang, Chengzhe Lu, Dawei Yan, Wei Dong, and Qingsen Yan,  “Dualbln: Dual branch lut-aware network for real-time image retouching,”  in Proceedings of the Asian Conference on Computer Vision, 2022, pp. 2139–2155.
  * [12] Tao Wang, Yong Li, Jingyang Peng, Yipeng Ma, Xian Wang, Fenglong Song, and Youliang Yan,  “Real-time image enhancer via learnable spatial-aware 3d lookup tables,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 2471–2480.
  * [13] Younghyun Jo and Seon Joo Kim,  “Practical single-image super-resolution using look-up table,”  in The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.
  * [14] Biting Yu, Luping Zhou, Lei Wang, Wanqi Yang, Ming Yang, Pierrick Bourgeat, and Jurgen Fripp,  “Sa-lut-nets: Learning sample-adaptive intensity lookup tables for brain tumor segmentation,”  IEEE Transactions on Medical Imaging, vol. 40, no. 5, pp. 1417–1427, 2021.
  * [15] Ting Jiang, Chuan Wang, Xinpeng Li, Ru Li, Haoqiang Fan, and Shuaicheng Liu,  “Meflut: Unsupervised 1d lookup tables for multi-exposure image fusion,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2023, pp. 10542–10551.
  * [16] Longguang Wang, Xiaoyu Dong, Yingqian Wang, Li Liu, Wei An, and Yulan Guo,  “Learnable lookup table for neural network quantization,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2022, pp. 12423–12433.
  * [17] Sharma Gaurav,  “The ciede2000 color-difference formula: Implementation notes, supplementary test data, and mathematical observations,”  COLOR research and application, vol. 30, no. 1, pp. 21–30, 2005.