ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics

The most natural approach to modelling parallel flips is a round-by-round progression. We need to keep the state of each edge across intermediate parallel flips.

We model the state transition of an edge $e$ over $k$ parallel flips using XOR operations. Let $e^0,e^k\in \{0,1\}$ denote the presence of $e$ in the initial and final triangulations, respectively. Let $\{q_1,\mathrm{\dots },q_g\}$ be the set of all potential convex empty quadrilaterals that share $e$ as a diagonal. We let $f_i^j\in \{0,1\}$ indicate whether a flip is performed on $q_i$ during step $j$.

Because the final state of edge $e$ after $k$ parallel flips is simply its initial state XORed with all intermediate flips across its potential quadrilaterals $q_{1\mathrm{\dots }g}$, we add the constraint

We decided to use the CryptoMiniSat5 [8] solver, since it supports inputs with XOR clauses.

To establish a lower bound, we first compute exact pairwise parallel flip distances $D_{i,j}$ using our SAT formulation. Any valid central triangulation at distances $d_k$ to inputs $T_k$ must satisfy the triangle inequality $d_i+d_j\ge D_{i,j}$ for all pairs $i,j$. To test if a target total distance $S$ is feasible, we find all integer assignments $(d_1,\mathrm{\dots },d_m)$ summing to $S$ that satisfy these pairwise constraints via recursive backtracking. For instances with $m=20$ triangulations, we use some further pruning techniques. We compute the minimum parallel flip distance $s_{dist}(i)$ for the last $i$ triangulations, for $i\ge i_{start}$, where we used $i_{start}=11$ for most instances since it was experimentally found to be sufficiently fast to compute. Then we use those suffix distances by pruning a branch whenever . Moreover, after the first $10$ and $15$ distances have been assigned recursively, we prune the branch if the prefix is not satisfiable.

The upper bound search is existential. Consequently, prioritizing candidates that are more likely to be satisfiable can significantly accelerate the search.

Let $d=(d_1,\mathrm{\dots },d_n)$ represent a potential assignment vector. We define the scoring function $𝒮(d)$ as the sum of absolute differences between all pairs of elements: $𝒮(d)={\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n|d_i-d_j|$. The candidate distributions are processed in ascending order of $𝒮(d)$.

Empirical analysis reveals that this heuristic is remarkably effective for randomly generated instances. In the majority of cases, the satisfiable distribution corresponds to the candidate with the minimal $𝒮(d)$ score. Even in cases where the global minimum is not the solution, the valid assignment is consistently found among the top-ranked candidates.

To transform a triangulation $T$ into another $T^{\prime }$, we flip edges such that the number of intersecting edges decreases. We now describe how, at each step, we choose a subset of independent edges to flip among the ones that reduce the number of intersections.

Firstly, we choose edges that, if flipped, introduce an edge that is present in $T^{\prime }$. To do so, we start by creating a graph containing those edges, where the nodes correspond to faces incident to them. Then we compute an edge coloring of this graph using the Misra and Gries algorithm [5] from the Boost Graph Library [6]. Finally, we flip the edges corresponding to the color class of maximum cardinality, and all the isolated edges. Since the boundary edges cannot be flipped, and the bounded faces are triangles, the maximum degree $\mathrm{\Delta }$ is at most $3$. Since the Misra and Gries algorithm uses at most $\mathrm{\Delta }+1\le 4$ colors, at least one fourth of the edges in the graph are flipped.

Secondly, we greedily pick the edges that are independent from all the edges that have already been picked, in order of non-increasing reduction of the number of intersections.

This transforms a triangulation into the other in a finite number of steps, since it can be seen as an adaptation to parallel flips of the algorithm described by Hanke, Ottmann, and Schuierer [3]. Given the flip sequence $ℱ=\{F_1,F_2,\mathrm{\dots },F_{|ℱ|-1}\}$ that we obtain with the described heuristic, let $\{{\tau }_0=T,{\tau }_1,\mathrm{\dots },{\tau }_{|ℱ|-1}=T^{\prime }\}$ be the corresponding sequence of triangulations, where ${\tau }_{k+1}$ is the triangulation we obtain after the parallel flip $F_k$. The reversed flip sequence ${ℱ}^{\prime }$ transforms $T^{\prime }$ into $T$ and it can be obtained by reversing the order of the parallel flips, and replacing each individual flip $e\to e^{\prime }$ with $e^{\prime }\to e$.

We can obtain other heuristic flip sequences ${ℱ}_k$, with $k\in [0,|ℱ|-1]$, by concatenating the heuristic flip sequence that turns $T$ into ${\tau }_k$ with the reversed flip sequence that turns $T^{\prime }$ into ${\tau }_k$.

Since these sequences are heuristic, their length might differ, and so we try multiple values of $k$ and choose the shortest flip sequence.

We empirically observed that trying all intermediate $k$ values typically reduces each triangulation’s distance by 1. Therefore, to maintain computational efficiency on large instances, we only do this when the total distance is within $currentBest+m$. Here, $currentBest$ is the smallest objective value among all the centers that were computed before.

Apart from input triangulations, we also generate candidate centers by greedily flipping edges in input triangulations to minimize total intersections with the entire point set until a local optimum is reached.

We then record all the intermediate triangulations at the end of each parallel flip, which is used to transform an input triangulation into one of those centers. To avoid trying all centers, we sort them in increasing order of total number of intersections with all the input triangulations and only compute the heuristic parallel flip distance for a fraction of them.

A promising combined strategy involves using the heuristic to select a candidate center triangulation, denoted as $T_{heur}$, and using the exact SAT solver to compute the minimal parallel flip distances from all input triangulations to $T_{heur}$, one by one.

Although this approach remains heuristic, it was effective on the rirs instances, but it also indirectly helped significantly with large non-rirs instances. Finding a slightly better solution allows the exact solver to handle cases that were previously out of reach.

A natural extension to computing pairwise distances is to compute exact distances for larger subsets. This yielded negligible improvements to the lower bound, likely due to the triangle inequality holding strong even for pairwise constraints.

Similar reasoning proved highly effective for the woc (especially tsplib) instances, observing that the distances to the optimal center were not uniformly distributed. By identifying and excluding outlier triangulations, we could exactly solve for the center of the remaining subset. This produced a robust heuristic center for the fixed center heuristic.