Shadoks Approach to Parallel Reconfiguration of Triangulations Journal: An instance is a collection of triangulations of a common point set. We must select a center triangulation and find short parallel-flip paths from each input triangulation to the center, minimizing the sum of path lengths. Journal: We present a SAT encoding for bounded-length paths and a global formulation for fixed path-length vectors. We discuss how these components interact in practice and summarize the performance of our solvers on the benchmark instances. Journal: and heuristics Journal: Nevertheless, we also developed heuristics that do not rely on any external solver, which are important to find initial solutions to large instances, which are then improved by roughly 10 % 10\% using SAT and MaxSAT solvers. Journal: We describe our exact algorithms in Section 2 , the heuristics in Section , and discuss the results we obtained in Section 3 . Concluding remarks and open problems are presented in Section . Journal: This section describes all elements of our exact solver, many of which are also used in the heuristic solvers. We first show how to use a SAT solver to compute shortest paths between two triangulations (Section 2.1 ). We then show how to extend this result to test if a solution with a list of path lengths exists (Section 2.2 ). We show how to obtain lower bounds in Section 2.3 and put the previous elements together to describe our exact solver in Section 2.4 . Journal: Notice that we can eliminate e ( u , v , 0 ) e(u,v,0) for u v ∉ T 0 uv\notin T_{0} and e ( u , v , ℓ ) e(u,v,\ell) for u v ∉ T ℓ uv\notin T_{\ell} . This is, however, only a special case of a more general rule. Journal: Proof. Consider the sequence L L of edges of T T crossed by s s in the order they cross the segment s s . A parallel flip cannot remove two consecutive edges of L L because they share a triangle, hence the theorem follows. ∎ Journal: We have the following theorem. Journal: Proof. Let d i , j d_{i,j} denote the distance between the input triangulations 𝐓 i , 𝐓 j \mathbf{T}_{i},\mathbf{T}_{j} . Let C C be a potential center and let r i r_{i} be the distance from C C to 𝐓 i \mathbf{T}_{i} . Consider a cycle 𝐓 1 , … , 𝐓 k \mathbf{T}_{1},\ldots,\mathbf{T}_{k} in the cycle packing. By triangle inequality d i , i + 1 ≤ r i + r i + 1 d_{i,i+1}\leq r_{i}+r_{i+1} with indices taken modulo k k (see Figure 3 (b)). Summing over the inequalities for i i from 1 1 to k k , we have that the length of the cycle is at most 2 ∑ i r i 2\sum_{i}r_{i} . Applying the same argument to every cycle, the theorem follows. ∎ Journal: 4 Heuristics In this section, we describe different approaches that can be used when we do not need to guarantee the optimality of the solution. In Section 2.5 , we present a conjecture that allows us to significantly increase the performance of the SAT solver. In Section , we show how to further increase the performance of the SAT solver using a heuristic coupled with some instance-independent preprocessed data. In Section , we show how to use the SAT solver to improve existing solutions. In Sections and , we respectively show how to compute short paths and good solutions without a SAT solver. Journal: Enforcing that an edge never disappears and later reappears along a path actually makes the SAT formulation harder to solve. However, there are some implications of the conjecture that are very useful to make the SAT formulation shorter and easier to solve. Journal: 4.1 Crossing Lower Bound Let b ( u v , T 0 ) b(uv,T_{0}) denote the number of parallel flips needed to obtain an edge u v uv starting at a triangulation T 0 T_{0} . Clearly, when creating the SAT formulation for a path T 0 , T 1 , … T_{0},T_{1},\ldots we only need to define the edge variable e ( u , v , i ) e(u,v,i) for i ≥ b ( T 0 , u v ) i\geq b(T_{0},uv) . Theorem 1 implies that if an edge u v uv crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} , then b ( u v , T 0 ) ≥ ⌈ log 2 ( χ ( u v , T 0 ) + 1 ) ⌉ b(uv,T_{0})\geq\lceil\log_{2}(\chi(uv,T_{0})+1)\rceil . This bound is tight when all the edges of T 0 T_{0} that cross u v uv share a common endpoint and the endpoints are in convex position (Figure ). However, there are different ways in which the edges of T 0 T_{0} may cross u v uv that may imply higher values of b ( u v , T 0 ) b(uv,T_{0}) . Figure 5: A path of length 3 3 to insert an edge that had 6 6 crossings. We consider estimations of b ( u v , T 0 ) b(uv,T_{0}) based on the sequence of triangles that contain an upper or a lower edge (Figure ). An edge u v uv that crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} is translated into a string s = s ( u v , T 0 ) s=s(uv,T_{0}) of χ ( u v , T 0 ) + 1 \chi(uv,T_{0})+1 symbols in the alphabet { ▼ , ▲ , ⊲ , ⊳ } \{\blacktriangledown,\blacktriangle,\triangleleft,\triangleright\} , according to which sides of u v uv contain the edges that are not crossed by u v uv in each triangle. Figure 6: A path of length 4 4 to insert an edge that had 6 6 crossings. Each triangle is labeled and colored as containing an upper or a lower edge. The unit flips on T 0 T_{0} have equivalent replacements on s s that replace the substring on the left-hand side by the substring on the right-hand side . We define a substring as a contiguous subsequence. Flipping the two extreme triangles translates to the extreme replacements ⊲ ▲ → ⊲ \triangleleft\blacktriangle\rightarrow\triangleleft , ⊲ ▼ → ⊲ \triangleleft\blacktriangledown\rightarrow\triangleleft , ▲ ⊳ → ⊳ \blacktriangle\triangleright\rightarrow\triangleright , and ▼ ⊳ → ⊳ \blacktriangledown\triangleright\rightarrow\triangleright . Flipping intermediate triangles with the same orientation translates to ▲ ▲ → ▲ \blacktriangle\blacktriangle\rightarrow\blacktriangle and ▼ ▼ → ▼ \blacktriangledown\blacktriangledown\rightarrow\blacktriangledown , while flipping intermediate triangles of different orientations translates to ▼ ▲ → ▲ ▼ \blacktriangledown\blacktriangle\rightarrow\blacktriangle\blacktriangledown and ▲ ▼ → ▼ ▲ \blacktriangle\blacktriangledown\rightarrow\blacktriangledown\blacktriangle . The last flip to insert the edge u v uv is ⊲ ⊳ → ∅ \triangleleft\triangleright\rightarrow\emptyset . There are other replacements that may increase the string length such as ▲ → ▲ ▲ \blacktriangle\rightarrow\blacktriangle\blacktriangle , which consist of exchanging the left-hand and right-hand side of some aforementioned replacements, but we show that we can always obtain shortest paths without using them. A parallel flip means that we may apply several replacements simultaneously as long as their left-hand sides correspond to disjoint substrings. We call the application of several replacements a rewriting , and use the notation s ⇒ s ′ s\Rightarrow s^{\prime} to say that s ′ s^{\prime} is a rewriting of s s . A rewriting sequence of length ℓ \ell is a sequence of ℓ + 1 \ell+1 strings connected by rewriting operations and ending at the empty string ∅ \emptyset . We want to find shortest rewriting sequences. Let b ( s ) b(s) be the length of the shortest rewriting sequence of the string s s . Notice that if the points are not in convex position, then some replacements may correspond to invalid flips. Hence, assuming convex position provides a lower bound b ( s ( u v , T 0 ) ) ≤ b ( u v , T 0 ) b(s(uv,T_{0}))\leq b(uv,T_{0}) . Furthermore, the replacements assume that there is an unbounded number of points, so that new triangles may be created freely. We say that a string s s is a subword of a string s ′ s^{\prime} if s s may be obtained from s ′ s^{\prime} by removing ▼ , ▲ \blacktriangledown,\blacktriangle symbols without changing the order of the remaining symbols. We prove the following results. Theorem 4 . If s s is a subword of s ′ s^{\prime} , then b ( s ) ≤ b ( s ′ ) b(s)\leq b(s^{\prime}) . Proof. Let s s be a subword of s ′ s^{\prime} and consider a shortest rewriting sequence s 0 ′ ⇒ ⋯ ⇒ s b ( s ′ ) ′ s^{\prime}_{0}\Rightarrow\cdots\Rightarrow s^{\prime}_{b(s^{\prime})} of the string s ′ s^{\prime} (we have s 0 ′ = s ′ s^{\prime}_{0}=s^{\prime} and s b ( s ′ ) ′ = ∅ s^{\prime}_{b(s^{\prime})}=\emptyset ). We show how to build a rewriting sequence s 0 ⇒ ⋯ ⇒ s b ( s ′ ) s_{0}\Rightarrow\cdots\Rightarrow s_{b(s^{\prime})} of s s of the same length (we have s 0 = s s_{0}=s and s b ( s ′ ) = ∅ s_{b(s^{\prime})}=\emptyset ). We show that s i s_{i} is a subword of s i ′ s^{\prime}_{i} for all i i . The proof proceeds by induction. The statement is true for i = 0 i=0 , since s s is a subword of s ′ s^{\prime} . Assume that s i s_{i} is a subword of s i ′ s^{\prime}_{i} . We build s i + 1 s_{i+1} as follows: the replacements applied to s i ′ s^{\prime}_{i} involving symbols which are all in s i s_{i} are applied to s i s_{i} to obtain s i + 1 s_{i+1} . All the other replacements are not taken into account to obtain s i + 1 s_{i+1} . We now show that the string s i + 1 s_{i+1} computed this way is a subword of s i + 1 ′ s^{\prime}_{i+1} . There are different types of replacements that we applied to s i ′ s^{\prime}_{i} but not to s i s_{i} . For convenience, the symbols of a word s i s_{i} that are not in the subword s i ′ s^{\prime}_{i} are called extra symbols and shown as gray symbols ▼ , ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown},{\color[rgb]{0.35,0.35,0.35}\blacktriangle} . • Replacements with one extra symbol of the form ▼ ▼ → ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangledown\rightarrow\blacktriangledown , ▼ ▼ → ▼ \blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow\blacktriangledown , ▲ ▲ → ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangle\rightarrow\blacktriangle , ▲ ▲ → ▲ \blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow\blacktriangle , ⊲ ▼ → ⊲ \triangleleft{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow\triangleleft , ⊲ ▲ → ⊲ \triangleleft{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow\triangleleft , ▼ ⊳ → ⊳ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\triangleright\rightarrow\triangleright , and ▲ ⊳ → ⊳ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\triangleright\rightarrow\triangleright . Regarding the correspondence between s i + 1 s_{i+1} and s i + 1 ′ s^{\prime}_{i+1} , the fact that this replacement is not applied to s i s_{i} means that the extra symbol ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown} or ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle} has been removed. • Replacements with one extra symbol of the form ▲ ▼ → ▼ ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangledown\rightarrow\blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangle} , ▼ ▲ → ▲ ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangle\rightarrow\blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangledown} , ▲ ▼ → ▼ ▲ \blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangle , and ▼ ▲ → ▲ ▼ \blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangledown . Regarding the correspondence between s i + 1 s_{i+1} and s i + 1 ′ s^{\prime}_{i+1} , the extra symbol ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle} or ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown} has just changed its position in the string s i + 1 s_{i+1} . • Replacements containing only extra-symbols are simply not taken into account. Hence, the theorem follows by induction. ∎ Corollary 5 . For every string s s , there exists a shortest rewriting sequence from s s that uses no replacement with the right-hand side longer than the left-hand side. Proof. Consider a rewriting sequence s 0 ′ , … , s b ( s ) ′ s^{\prime}_{0},\ldots,s^{\prime}_{b(s)} that applies a replacement with the right-hand side longer than the left-hand side from s i ′ s^{\prime}_{i} to s i + 1 ′ s^{\prime}_{i+1} and let i i be the smallest such value. Let s s be the string obtained from s i ′ s^{\prime}_{i} applying the subset of replacements that exclude the ones with the right-hand side longer than the left-hand side. We have that s s is a subword of s i + 1 ′ s^{\prime}_{i+1} . By Theorem , b ( s ) ≤ b ( s i + 1 ′ ) b(s)\leq b(s^{\prime}_{i+1}) , and the corollary follows. ∎ Corollary 6 . For every string s s of length at least 3 3 , there exists a shortest rewriting sequence from s s where every rewriting contains two extreme replacements. Proof. Consider a shortest rewriting sequence s ⇒ s 1 ⇒ ⋯ s\Rightarrow s_{1}\Rightarrow\cdots that does not start with a left removal ⊲ ▼ → ⊲ \triangleleft\blacktriangledown\rightarrow\triangleleft or ⊲ ▲ → ⊲ \triangleleft\blacktriangle\rightarrow\triangleleft . Assume without loss of generality that the string s s starts with ⊲ ▼ \triangleleft\blacktriangledown , since the case of ⊲ ▲ \triangleleft\blacktriangle is analogous. The case of the extreme replacement involving ⊳ \triangleright is also analogous. Consider the different rewritings from s s to s 1 s_{1} : • If the rewriting is ⊲ ▼ X ⇒ ⊲ ▼ Y \triangleleft\blacktriangledown X\Rightarrow\triangleleft\blacktriangledown Y for strings X , Y X,Y where the leftmost ▼ \blacktriangledown is not involved in any replacement, then the length of the full rewriting sequence is 1 + b ( ⊲ ▼ Y ) 1+b(\triangleleft\blacktriangledown Y) . We now show how to obtain a rewriting of the same length that starts with an extreme replacement. We rewrite ⊲ ▼ X ⇒ ⊲ Y \triangleleft\blacktriangledown X\Rightarrow\triangleleft Y providing a sequence of total length 1 + b ( ⊲ Y ) 1+b(\triangleleft Y) . By Theorem , we have b ( ⊲ Y ) ≤ b ( ⊲ ▼ Y ) b(\triangleleft Y)\leq b(\triangleleft\blacktriangledown Y) . • If the rewriting is ⊲ ▼ ▼ X ⇒ ⊲ ▼ Y \triangleleft\blacktriangledown\blacktriangledown X\Rightarrow\triangleleft\blacktriangledown Y for strings X , Y X,Y where the leftmost replacement is ▼ ▼ → ▼ \blacktriangledown\blacktriangledown\rightarrow\blacktriangledown , then we obtain the same string ⊲ ▼ Y \triangleleft\blacktriangledown Y if we apply the replacement ⊲ ▼ → ▼ \triangleleft\blacktriangledown\rightarrow\blacktriangledown . • If the rewriting is ⊲ ▼ ▲ X ⇒ ⊲ ▲ ▼ Y \triangleleft\blacktriangledown\blacktriangle X\Rightarrow\triangleleft\blacktriangle\blacktriangledown Y for strings X , Y X,Y where the leftmost replacement is ▼ ▲ → ▲ ▼ \blacktriangledown\blacktriangle\rightarrow\blacktriangle\blacktriangledown , then the length of the full rewriting sequence is 1 + b ( ⊲ ▲ ▼ Y ) 1+b(\triangleleft\blacktriangle\blacktriangledown Y) . We now show how to obtain a rewriting of the same length that starts with an extreme replacement. We rewrite ⊲ ▼ ▲ X ⇒ ⊲ ▲ Y \triangleleft\blacktriangledown\blacktriangle X\Rightarrow\triangleleft\blacktriangle Y providing a sequence of total length 1 + b ( ⊲ ▲ Y ) 1+b(\triangleleft\blacktriangle Y) . By Theorem , we have b ( ⊲ ▼ Y ) ≤ b ( ⊲ ▲ ▼ Y ) b(\triangleleft\blacktriangledown Y)\leq b(\triangleleft\blacktriangle\blacktriangledown Y) .∎ We use a heuristic together with a depth first search exact solution to estimate b ( s ) b(s) . The heuristic is very involved and sometimes gives incorrect bounds. To fix some wrong bounds, we use an instance-independent preprocessing to compute tight values of b ( s ) b(s) for small enough strings s s and store only the values where the heuristic incorrectly computes b ( s ) b(s) in a file. This file is loaded by our solver and stored in a hash table. Journal: 4.2 Improving a Solution Given a solution P 1 , … , P | 𝒯 | P_{1},\ldots,P_{|\mathcal{T}|} , we may improve it as follows. We choose a random path P i P_{i} and use the SAT formulation to find a solution where the length of P i P_{i} is decremented and all other lengths remain the same. We repeat this as often as necessary. Notice that the method may converge to a locally optimal minimal list of lengths that is not globally optimal. If the number of clauses is too large, there are two different approaches that we can take (and they may be combined). We may force the new solution to be close to the original one by only creating edge variables that cross few edges in the corresponding triangulation of the previous solution. We may also trim the solution to a certain radius r r , by only rebuilding the portion of the solution that is within r r steps from the center. In this case, it is helpful to use MaxSAT first, in order to reduce the number of unit-flips performed in the last steps as follows. Given a path T 0 , … , T ℓ T_{0},\ldots,T\ell , we first use a MaxSAT solver to find the path of length ℓ \ell that minimizes the number of unit flips performed from T ℓ − 1 T_{\ell-1} to T ℓ T_{\ell} . The MaxSAT formulation is equal to the SAT formulation with soft clauses ¬ f ( u , v , u 2 , v 2 , ℓ ) \neg f(u,v,u_{2},v_{2},\ell) for each last step flip variable. We then find the path of length ℓ − 1 \ell-1 from T 0 T_{0} to the T ℓ − 1 T_{\ell-1} of the previosu path that minimizes the number of unit flips performed from T ℓ − 2 T_{\ell-2} to T ℓ − 1 T_{\ell-1} . We continue this way for r r steps. 4.3 Path Heuristic The SAT formulation finds the shortest path connecting two triangulations reasonably fast, but it may be too slow for some usages. We also designed a heuristic that produces reasonably short paths quickly. We are given two triangulations T 0 , T ′ T_{0},T^{\prime} and the goal is to find a short path from T 0 T_{0} to T ′ T^{\prime} . We use a greedy approach that iteratively obtains a triangulation T i + 1 T_{i+1} from a triangulation T i T_{i} as follows. Let F F denote the set of possible unit flips in T i T_{i} . More precisely, the elements of F F are pairs e , e ′ e,e^{\prime} of edges such that a unit flip from T i T_{i} removes e e and inserts e ′ e^{\prime} . We then build a graph G ( F ) G(F) with vertex set F F and edges between two unit flips that share a triangle. Notice that the possible parallel flips correspond to independent sets in G ( F ) G(F) . We assign a weight to the vertices as follows. The weight of a vertex e , e ′ e,e^{\prime} is the number of edges in T ′ T^{\prime} crossed by e ′ e^{\prime} minus the number of edges in T ′ T^{\prime} crossed by e e . Vertices of zero or negative weight are eliminated. We then proceed to greedily find an independent set I I in G ( F ) G(F) . We iteratively add to I I the unmarked vertex of maximum weight, breaking ties by minimum degree. We then mark all the vertices in the closed neighborhood of I I . We repeat until all vertices are marked. This iterative approach is repeated until we reach T ′ T^{\prime} , which will happen in O ( n 2 ) O(n^{2}) flips because of the following Theorem from [ 10 ] . Theorem 7 . Let T , T ′ T,T^{\prime} be two triangulations of the same point set. If T ≠ T ′ T\neq T^{\prime} , then there exists a unit flip that replaces an edge e ∈ T e\in T by an edge e ′ e^{\prime} such that e e crosses more edges of T ′ T^{\prime} than e ′ e^{\prime} does. We further improve the heuristic using the squeaky wheel paradigm [ 11 ] . Initially, we assign weight 1 1 to every edge. We modify the definition of the weight of a flip as follows. The weight of a flip e , e ′ e,e^{\prime} is the sum of the weights of the edges in T ′ T^{\prime} crossed by e ′ e^{\prime} minus the sum of the weights of the edges in T ′ T^{\prime} crossed by e e . When we reach triangulation T i + 1 = T ′ T_{i+1}=T^{\prime} from a triangulation T i T_{i} we increment the weight of all edges in T ′ T^{\prime} that are not in T i + 1 T_{i+1} . We repeat the greedy algorithm with the new weights, keeping the best solution found. This procedure is repeated multiple times. Journal: 4.4 Solution Heuristic We use the following strategy to obtain reasonably good initial solutions that we may use as a basis to improve with the aforementioned methods. We start by adding the Delaunay triangulation as a candidate center. We then build other candidate centers by performing flips starting from the Delaunay triangulation. Given an edge e e and a triangulation T T , let χ ( e , T ) \chi(e,T) denote the number of segments of T T crossed by e e . We repeatedly perform unit flips that remove an edge e e and add an edge e ′ e^{\prime} maximizing ∑ T ∈ 𝒯 χ ( e ) p − χ ( e ′ ) p , \sum_{T\in\mathcal{T}}\chi(e)^{p}-\chi(e^{\prime})^{p}, as long as the value of the sum is positive. We add the triangulation we obtained to the set of candidate center and repeat the process for a different value of p p . We calculate the paths from the candidate centers to each solution, building a solution pool. For the next step it will be useful to have a small number of unit-flips in the last flip of the path from the input triangulation to the center. To do that, we either use the greedy heuristic or a MaxSAT formulation. To improve the solution pool, we pick a solution from the pool and look at the triangulations that are one flip away from the center in each path. For each such triangulation, we compute the distance to the input triangulations and add the solution to the pool as before. Journal: In Section , we present the heuristics used to find solutions to the instances that we could not solve exactly. Journal: Greedy Greedy Squeaky Squeaky SAT SAT forward backward forward backward happy exact n n ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t 500 13 4.2 12 3.7 13 45 12 18 12 1512 12 10191 1000 12 7.8 12 6.8 12 25 12 38 11 6806 11 78264 1500 13 13 12 12 12 52 12 23 11 19302 11 201353 2000 15 21 13 18 13 65 13 104 13 16937 13 485177 3000 15 36 15 33 14 193 15 433 14 140729 ⋅ \cdot ⋅ \cdot 4000 18 57 16 51 16 577 15 655 15 101402 ⋅ \cdot ⋅ \cdot 5000 18 70 17 70 16 238 17 278 16 1037840 ⋅ \cdot ⋅ \cdot 6000 17 93 16 83 17 1071 16 644 16 271081 ⋅ \cdot ⋅ \cdot 7000 17 94 17 96 17 180 17 407 16 471389 ⋅ \cdot ⋅ \cdot Table 1: Length and computation time (in milliseconds) from the Delaunay triangulation to the first input triangulation of the rirs- n n - -20 instance for different values of the number of points n n . The columns respectively correspond to the greedy heuristic forward and backward, the squeaky wheel heuristic forward and backward, the SAT solution with the happy edges conjecture, and the SAT solution without the happy edges conjecture, unless it takes too long. Journal: The best lengths found are shown in bold. Journal: The best lengths found are shown in bold. Journal: In this section, we use the Delaunay triangulation as one extreme, because it is a well defined triangulation that makes a reasonably good (but not very good) center. Table shows the length of the path and the running time of different heuristics and SAT solutions with and without the happy edges conjecture. The paths are calculated from the Delaunay triangulation to the first input triangulation of several instances. The SAT paths are obtained by first running the squeaky wheel heuristic in both directions, and then iteratively decreasing the path length. Notice that the running time of the heuristics is much smaller, while the result is rarely more than 1 1 unit away from the optimal distance, especially if we take the minimum of both directions. We run the squeaky wheel heuristic for at most 16 16 iterations, but stop earlier if the length increases from one iteration to the next. Journal: We now present the exact solver that we used to solve most instances exactly. Journal: Notice that the impact of the happy edges conjecture is less significant than when computing only paths, as there are few common edges on all input triangulations. We remark that during the competition, we managed to find exact solutions to 189 189 of the 201 201 small instances without assuming the happy edges conjecture. Journal: 4.5 Crossing Lower Bound The heuristic that estimates b ( s ) b(s) for a string s s (see Section ) is surprisingly accurate. Figure shows the heuristic error rates for different string lengths. The smallest strings where the heuristic fails have length 12 12 and are: ⊲ ? ▼ ▲ ▲ ▼ ▲ ▲ ▲ ▲ ? ⊳ \triangleleft?\blacktriangledown\blacktriangle\blacktriangle\blacktriangledown\blacktriangle\blacktriangle\blacktriangle\blacktriangle?\triangleright , ⊲ ? ▲ ▼ ▼ ▲ ▼ ▼ ▼ ▼ ? ⊳ \triangleleft?\blacktriangle\blacktriangledown\blacktriangledown\blacktriangle\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown?\triangleright , ⊲ ? ▲ ▲ ▲ ▲ ▼ ▲ ▲ ▼ ? ⊳ \triangleleft?\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangledown\blacktriangle\blacktriangle\blacktriangledown?\triangleright , and ⊲ ? ▼ ▼ ▼ ▼ ▲ ▼ ▼ ▲ ? ⊳ \triangleleft?\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangle\blacktriangledown\blacktriangledown\blacktriangle?\triangleright , with the question marks replaced by ▼ \blacktriangledown or ▲ \blacktriangle , which gives an error rate of 4 ⋅ 4 / 2 10 ≈ 0.016 4\cdot 4/2^{10}\approx 0.016 as the two extreme symbols are fixed. We compare the error rate when the heuristic uses exact preprocessed values to solve subproblems and when the heuristic does not use any preprocessed data. The heuristic was never wrong by more than one unit on strings of up to 28 28 symbols. Figure 7: Error rate of the crossing lower bound for strings with k k symbols, which corresponds to k − 1 k-1 crossings. 4.6 Heuristic Solutions The typical process to solve instances that we did not solve exactly consists of several steps. First, we use the heuristic from Section to obtain a reasonably good center. Notice that no SAT solver is used in this part. The evolution of the objective value for this step is shown in Figure . The name of the rirs instances is composed of two values. The first is the number of points and the second is the number of input triangulations. Figure 8: Evolution of the best solution found by the heuristic solver without any SAT solver for different instances. Second, we build a new solution that keeps the same center but we recalculate the paths using the SAT formulation from 2.1 , assuming the happy edges conjecture (Section 2.5 ) and inexact lower bounds (Section ). This will typically reduce the objective value by 1 1 to 4 4 percent. The calculation of 50 50 paths in each solution is shown in Figure . Notice that the running time increases rapidly with the number of points and that finding a shorter path (satisfiable SAT problem) is typically slower than when no shorter path exists (unsatisfiable SAT problems). Figure 9: Path by path improvement of the heuristic solutions using a SAT solver, where each path is recalculated but the center is kept unchanged. Each black vertical bar represents the beginning of the computation of a path. Third, we improve the solution using the SAT formulation from Section 2.2 , assuming the happy edges conjecture (Section 2.5 ) and inexact lower bounds (Section ). This part requires adjusting a large number of parameters in order to obtain SAT problems that are not too hard. The parameters include the distance to the previous center, the distance to the previous path, and whether the solution will be trimmed. Optionally but recommended when the problem is trimmed, we use MaxSAT to reduce the number of unit flips close to the center. The improvement of some solutions over time is shown in Figure . Notice that there is a significant preprocessing time to calculate edge variables with a limited number of crossings. This preprocessing is applied initially and after every improvement. Also notice that unsatisfiable SAT problems, which mean no improvement in the solution, are solved much faster than satisfiable ones. Figure 10: Improvement of the whole solution using a SAT solver and reducing the length of a random path by one unit at a time. We constrain the edges in the new solution to cross at most 3 3 edges of the corresponding triangulation in the solution (except for the instance rirs-500-20 , where the slower but more effective execution with the parameter set to at most 7 7 edges is also pictured) but do not use trimming. Each black vertical bar represents a new path length that we try to decrement. Journal: 5 Conclusion and Open Problems We were surprised that we managed to solve so many instances exactly and how well an heuristic approximates the exact distance. We believe the following factors help explain the strong practical performance: • The short path length that allows a somewhat small number of variables. • A SAT model where most clauses have size 2 2 . • The ability to eliminate many variables through several arguments. • The fact that the happy edges conjecture is either true or at least holds in most practical cases. The short path lengths are somewhat surprising, given that an Ω ( n ) \Omega(n) lower bound is presented in [ 9 ] , in contrast to the Θ ( log n ) \Theta(\log n) bound for combinatorial triangulations [ 12 ] , where we are allowed to flip non-convex quadrilaterals. In the challenge instances, we observed path lengths that are roughly O ( log n ) O(\log n) . Still, there are random instances with only 160 160 points and 20 20 input triangulations and woc instances with only 185 185 points and 6 6 triangulations that we could not solve exactly. Also, we still managed to improve solutions to instances with as few as 320 320 points and 20 20 input triangulations months after the beginning of the challenge. The challenge instances did not have many points in convex position. Surprisingly, the case where all points are in convex position is the hardest for our SAT formulation, as there are Θ ( n 4 ) \Theta(n^{4}) empty convex quadrilaterals. We wonder if a different model works better when all and also when most points are in convex position. We believe that the same problem with unit flips is significantly harder because the long path lengths make the SAT formulation much more complex and removing a happy edge can reduce a path length from Θ ( n 2 ) \Theta(n^{2}) to Θ ( n ) \Theta(n) . Many theoretical open problems remain, such as proving Conjecture 3 . We also wonder if parallel flip distance problem is NP-hard in general and in convex position, as well as the unit flip distance problem in the convex case (the problem is NP-hard for general point sets [ 14 ] ). We also do not know if the problem of calculating b ( s ) b(s) (see Section ) can be solved in polynomial time, possibly using dynamic programming.
Guilherme D. da Fonseca, Fabien Feschet, Yan Gerard · 2026
Read Shadoks Approach to Parallel Reconfiguration of Triangulations Journal: An instance is a collection of triangulations of a common point set. We must select a center triangulation and find short parallel-flip paths from each input triangulation to the center, minimizing the sum of path lengths. Journal: We present a SAT encoding for bounded-length paths and a global formulation for fixed path-length vectors. We discuss how these components interact in practice and summarize the performance of our solvers on the benchmark instances. Journal: and heuristics Journal: Nevertheless, we also developed heuristics that do not rely on any external solver, which are important to find initial solutions to large instances, which are then improved by roughly 10 % 10\% using SAT and MaxSAT solvers. Journal: We describe our exact algorithms in Section 2 , the heuristics in Section , and discuss the results we obtained in Section 3 . Concluding remarks and open problems are presented in Section . Journal: This section describes all elements of our exact solver, many of which are also used in the heuristic solvers. We first show how to use a SAT solver to compute shortest paths between two triangulations (Section 2.1 ). We then show how to extend this result to test if a solution with a list of path lengths exists (Section 2.2 ). We show how to obtain lower bounds in Section 2.3 and put the previous elements together to describe our exact solver in Section 2.4 . Journal: Notice that we can eliminate e ( u , v , 0 ) e(u,v,0) for u v ∉ T 0 uv\notin T_{0} and e ( u , v , ℓ ) e(u,v,\ell) for u v ∉ T ℓ uv\notin T_{\ell} . This is, however, only a special case of a more general rule. Journal: Proof. Consider the sequence L L of edges of T T crossed by s s in the order they cross the segment s s . A parallel flip cannot remove two consecutive edges of L L because they share a triangle, hence the theorem follows. ∎ Journal: We have the following theorem. Journal: Proof. Let d i , j d_{i,j} denote the distance between the input triangulations 𝐓 i , 𝐓 j \mathbf{T}_{i},\mathbf{T}_{j} . Let C C be a potential center and let r i r_{i} be the distance from C C to 𝐓 i \mathbf{T}_{i} . Consider a cycle 𝐓 1 , … , 𝐓 k \mathbf{T}_{1},\ldots,\mathbf{T}_{k} in the cycle packing. By triangle inequality d i , i + 1 ≤ r i + r i + 1 d_{i,i+1}\leq r_{i}+r_{i+1} with indices taken modulo k k (see Figure 3 (b)). Summing over the inequalities for i i from 1 1 to k k , we have that the length of the cycle is at most 2 ∑ i r i 2\sum_{i}r_{i} . Applying the same argument to every cycle, the theorem follows. ∎ Journal: 4 Heuristics In this section, we describe different approaches that can be used when we do not need to guarantee the optimality of the solution. In Section 2.5 , we present a conjecture that allows us to significantly increase the performance of the SAT solver. In Section , we show how to further increase the performance of the SAT solver using a heuristic coupled with some instance-independent preprocessed data. In Section , we show how to use the SAT solver to improve existing solutions. In Sections and , we respectively show how to compute short paths and good solutions without a SAT solver. Journal: Enforcing that an edge never disappears and later reappears along a path actually makes the SAT formulation harder to solve. However, there are some implications of the conjecture that are very useful to make the SAT formulation shorter and easier to solve. Journal: 4.1 Crossing Lower Bound Let b ( u v , T 0 ) b(uv,T_{0}) denote the number of parallel flips needed to obtain an edge u v uv starting at a triangulation T 0 T_{0} . Clearly, when creating the SAT formulation for a path T 0 , T 1 , … T_{0},T_{1},\ldots we only need to define the edge variable e ( u , v , i ) e(u,v,i) for i ≥ b ( T 0 , u v ) i\geq b(T_{0},uv) . Theorem 1 implies that if an edge u v uv crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} , then b ( u v , T 0 ) ≥ ⌈ log 2 ( χ ( u v , T 0 ) + 1 ) ⌉ b(uv,T_{0})\geq\lceil\log_{2}(\chi(uv,T_{0})+1)\rceil . This bound is tight when all the edges of T 0 T_{0} that cross u v uv share a common endpoint and the endpoints are in convex position (Figure ). However, there are different ways in which the edges of T 0 T_{0} may cross u v uv that may imply higher values of b ( u v , T 0 ) b(uv,T_{0}) . Figure 5: A path of length 3 3 to insert an edge that had 6 6 crossings. We consider estimations of b ( u v , T 0 ) b(uv,T_{0}) based on the sequence of triangles that contain an upper or a lower edge (Figure ). An edge u v uv that crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} is translated into a string s = s ( u v , T 0 ) s=s(uv,T_{0}) of χ ( u v , T 0 ) + 1 \chi(uv,T_{0})+1 symbols in the alphabet { ▼ , ▲ , ⊲ , ⊳ } \{\blacktriangledown,\blacktriangle,\triangleleft,\triangleright\} , according to which sides of u v uv contain the edges that are not crossed by u v uv in each triangle. Figure 6: A path of length 4 4 to insert an edge that had 6 6 crossings. Each triangle is labeled and colored as containing an upper or a lower edge. The unit flips on T 0 T_{0} have equivalent replacements on s s that replace the substring on the left-hand side by the substring on the right-hand side . We define a substring as a contiguous subsequence. Flipping the two extreme triangles translates to the extreme replacements ⊲ ▲ → ⊲ \triangleleft\blacktriangle\rightarrow\triangleleft , ⊲ ▼ → ⊲ \triangleleft\blacktriangledown\rightarrow\triangleleft , ▲ ⊳ → ⊳ \blacktriangle\triangleright\rightarrow\triangleright , and ▼ ⊳ → ⊳ \blacktriangledown\triangleright\rightarrow\triangleright . Flipping intermediate triangles with the same orientation translates to ▲ ▲ → ▲ \blacktriangle\blacktriangle\rightarrow\blacktriangle and ▼ ▼ → ▼ \blacktriangledown\blacktriangledown\rightarrow\blacktriangledown , while flipping intermediate triangles of different orientations translates to ▼ ▲ → ▲ ▼ \blacktriangledown\blacktriangle\rightarrow\blacktriangle\blacktriangledown and ▲ ▼ → ▼ ▲ \blacktriangle\blacktriangledown\rightarrow\blacktriangledown\blacktriangle . The last flip to insert the edge u v uv is ⊲ ⊳ → ∅ \triangleleft\triangleright\rightarrow\emptyset . There are other replacements that may increase the string length such as ▲ → ▲ ▲ \blacktriangle\rightarrow\blacktriangle\blacktriangle , which consist of exchanging the left-hand and right-hand side of some aforementioned replacements, but we show that we can always obtain shortest paths without using them. A parallel flip means that we may apply several replacements simultaneously as long as their left-hand sides correspond to disjoint substrings. We call the application of several replacements a rewriting , and use the notation s ⇒ s ′ s\Rightarrow s^{\prime} to say that s ′ s^{\prime} is a rewriting of s s . A rewriting sequence of length ℓ \ell is a sequence of ℓ + 1 \ell+1 strings connected by rewriting operations and ending at the empty string ∅ \emptyset . We want to find shortest rewriting sequences. Let b ( s ) b(s) be the length of the shortest rewriting sequence of the string s s . Notice that if the points are not in convex position, then some replacements may correspond to invalid flips. Hence, assuming convex position provides a lower bound b ( s ( u v , T 0 ) ) ≤ b ( u v , T 0 ) b(s(uv,T_{0}))\leq b(uv,T_{0}) . Furthermore, the replacements assume that there is an unbounded number of points, so that new triangles may be created freely. We say that a string s s is a subword of a string s ′ s^{\prime} if s s may be obtained from s ′ s^{\prime} by removing ▼ , ▲ \blacktriangledown,\blacktriangle symbols without changing the order of the remaining symbols. We prove the following results. Theorem 4 . If s s is a subword of s ′ s^{\prime} , then b ( s ) ≤ b ( s ′ ) b(s)\leq b(s^{\prime}) . Proof. Let s s be a subword of s ′ s^{\prime} and consider a shortest rewriting sequence s 0 ′ ⇒ ⋯ ⇒ s b ( s ′ ) ′ s^{\prime}_{0}\Rightarrow\cdots\Rightarrow s^{\prime}_{b(s^{\prime})} of the string s ′ s^{\prime} (we have s 0 ′ = s ′ s^{\prime}_{0}=s^{\prime} and s b ( s ′ ) ′ = ∅ s^{\prime}_{b(s^{\prime})}=\emptyset ). We show how to build a rewriting sequence s 0 ⇒ ⋯ ⇒ s b ( s ′ ) s_{0}\Rightarrow\cdots\Rightarrow s_{b(s^{\prime})} of s s of the same length (we have s 0 = s s_{0}=s and s b ( s ′ ) = ∅ s_{b(s^{\prime})}=\emptyset ). We show that s i s_{i} is a subword of s i ′ s^{\prime}_{i} for all i i . The proof proceeds by induction. The statement is true for i = 0 i=0 , since s s is a subword of s ′ s^{\prime} . Assume that s i s_{i} is a subword of s i ′ s^{\prime}_{i} . We build s i + 1 s_{i+1} as follows: the replacements applied to s i ′ s^{\prime}_{i} involving symbols which are all in s i s_{i} are applied to s i s_{i} to obtain s i + 1 s_{i+1} . All the other replacements are not taken into account to obtain s i + 1 s_{i+1} . We now show that the string s i + 1 s_{i+1} computed this way is a subword of s i + 1 ′ s^{\prime}_{i+1} . There are different types of replacements that we applied to s i ′ s^{\prime}_{i} but not to s i s_{i} . For convenience, the symbols of a word s i s_{i} that are not in the subword s i ′ s^{\prime}_{i} are called extra symbols and shown as gray symbols ▼ , ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown},{\color[rgb]{0.35,0.35,0.35}\blacktriangle} . • Replacements with one extra symbol of the form ▼ ▼ → ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangledown\rightarrow\blacktriangledown , ▼ ▼ → ▼ \blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow\blacktriangledown , ▲ ▲ → ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangle\rightarrow\blacktriangle , ▲ ▲ → ▲ \blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow\blacktriangle , ⊲ ▼ → ⊲ \triangleleft{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow\triangleleft , ⊲ ▲ → ⊲ \triangleleft{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow\triangleleft , ▼ ⊳ → ⊳ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\triangleright\rightarrow\triangleright , and ▲ ⊳ → ⊳ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\triangleright\rightarrow\triangleright . Regarding the correspondence between s i + 1 s_{i+1} and s i + 1 ′ s^{\prime}_{i+1} , the fact that this replacement is not applied to s i s_{i} means that the extra symbol ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown} or ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle} has been removed. • Replacements with one extra symbol of the form ▲ ▼ → ▼ ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangledown\rightarrow\blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangle} , ▼ ▲ → ▲ ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangle\rightarrow\blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangledown} , ▲ ▼ → ▼ ▲ \blacktriangle{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\rightarrow{\color[rgb]{0.35,0.35,0.35}\blacktriangledown}\blacktriangle , and ▼ ▲ → ▲ ▼ \blacktriangledown{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\rightarrow{\color[rgb]{0.35,0.35,0.35}\blacktriangle}\blacktriangledown . Regarding the correspondence between s i + 1 s_{i+1} and s i + 1 ′ s^{\prime}_{i+1} , the extra symbol ▲ {\color[rgb]{0.35,0.35,0.35}\blacktriangle} or ▼ {\color[rgb]{0.35,0.35,0.35}\blacktriangledown} has just changed its position in the string s i + 1 s_{i+1} . • Replacements containing only extra-symbols are simply not taken into account. Hence, the theorem follows by induction. ∎ Corollary 5 . For every string s s , there exists a shortest rewriting sequence from s s that uses no replacement with the right-hand side longer than the left-hand side. Proof. Consider a rewriting sequence s 0 ′ , … , s b ( s ) ′ s^{\prime}_{0},\ldots,s^{\prime}_{b(s)} that applies a replacement with the right-hand side longer than the left-hand side from s i ′ s^{\prime}_{i} to s i + 1 ′ s^{\prime}_{i+1} and let i i be the smallest such value. Let s s be the string obtained from s i ′ s^{\prime}_{i} applying the subset of replacements that exclude the ones with the right-hand side longer than the left-hand side. We have that s s is a subword of s i + 1 ′ s^{\prime}_{i+1} . By Theorem , b ( s ) ≤ b ( s i + 1 ′ ) b(s)\leq b(s^{\prime}_{i+1}) , and the corollary follows. ∎ Corollary 6 . For every string s s of length at least 3 3 , there exists a shortest rewriting sequence from s s where every rewriting contains two extreme replacements. Proof. Consider a shortest rewriting sequence s ⇒ s 1 ⇒ ⋯ s\Rightarrow s_{1}\Rightarrow\cdots that does not start with a left removal ⊲ ▼ → ⊲ \triangleleft\blacktriangledown\rightarrow\triangleleft or ⊲ ▲ → ⊲ \triangleleft\blacktriangle\rightarrow\triangleleft . Assume without loss of generality that the string s s starts with ⊲ ▼ \triangleleft\blacktriangledown , since the case of ⊲ ▲ \triangleleft\blacktriangle is analogous. The case of the extreme replacement involving ⊳ \triangleright is also analogous. Consider the different rewritings from s s to s 1 s_{1} : • If the rewriting is ⊲ ▼ X ⇒ ⊲ ▼ Y \triangleleft\blacktriangledown X\Rightarrow\triangleleft\blacktriangledown Y for strings X , Y X,Y where the leftmost ▼ \blacktriangledown is not involved in any replacement, then the length of the full rewriting sequence is 1 + b ( ⊲ ▼ Y ) 1+b(\triangleleft\blacktriangledown Y) . We now show how to obtain a rewriting of the same length that starts with an extreme replacement. We rewrite ⊲ ▼ X ⇒ ⊲ Y \triangleleft\blacktriangledown X\Rightarrow\triangleleft Y providing a sequence of total length 1 + b ( ⊲ Y ) 1+b(\triangleleft Y) . By Theorem , we have b ( ⊲ Y ) ≤ b ( ⊲ ▼ Y ) b(\triangleleft Y)\leq b(\triangleleft\blacktriangledown Y) . • If the rewriting is ⊲ ▼ ▼ X ⇒ ⊲ ▼ Y \triangleleft\blacktriangledown\blacktriangledown X\Rightarrow\triangleleft\blacktriangledown Y for strings X , Y X,Y where the leftmost replacement is ▼ ▼ → ▼ \blacktriangledown\blacktriangledown\rightarrow\blacktriangledown , then we obtain the same string ⊲ ▼ Y \triangleleft\blacktriangledown Y if we apply the replacement ⊲ ▼ → ▼ \triangleleft\blacktriangledown\rightarrow\blacktriangledown . • If the rewriting is ⊲ ▼ ▲ X ⇒ ⊲ ▲ ▼ Y \triangleleft\blacktriangledown\blacktriangle X\Rightarrow\triangleleft\blacktriangle\blacktriangledown Y for strings X , Y X,Y where the leftmost replacement is ▼ ▲ → ▲ ▼ \blacktriangledown\blacktriangle\rightarrow\blacktriangle\blacktriangledown , then the length of the full rewriting sequence is 1 + b ( ⊲ ▲ ▼ Y ) 1+b(\triangleleft\blacktriangle\blacktriangledown Y) . We now show how to obtain a rewriting of the same length that starts with an extreme replacement. We rewrite ⊲ ▼ ▲ X ⇒ ⊲ ▲ Y \triangleleft\blacktriangledown\blacktriangle X\Rightarrow\triangleleft\blacktriangle Y providing a sequence of total length 1 + b ( ⊲ ▲ Y ) 1+b(\triangleleft\blacktriangle Y) . By Theorem , we have b ( ⊲ ▼ Y ) ≤ b ( ⊲ ▲ ▼ Y ) b(\triangleleft\blacktriangledown Y)\leq b(\triangleleft\blacktriangle\blacktriangledown Y) .∎ We use a heuristic together with a depth first search exact solution to estimate b ( s ) b(s) . The heuristic is very involved and sometimes gives incorrect bounds. To fix some wrong bounds, we use an instance-independent preprocessing to compute tight values of b ( s ) b(s) for small enough strings s s and store only the values where the heuristic incorrectly computes b ( s ) b(s) in a file. This file is loaded by our solver and stored in a hash table. Journal: 4.2 Improving a Solution Given a solution P 1 , … , P | 𝒯 | P_{1},\ldots,P_{|\mathcal{T}|} , we may improve it as follows. We choose a random path P i P_{i} and use the SAT formulation to find a solution where the length of P i P_{i} is decremented and all other lengths remain the same. We repeat this as often as necessary. Notice that the method may converge to a locally optimal minimal list of lengths that is not globally optimal. If the number of clauses is too large, there are two different approaches that we can take (and they may be combined). We may force the new solution to be close to the original one by only creating edge variables that cross few edges in the corresponding triangulation of the previous solution. We may also trim the solution to a certain radius r r , by only rebuilding the portion of the solution that is within r r steps from the center. In this case, it is helpful to use MaxSAT first, in order to reduce the number of unit-flips performed in the last steps as follows. Given a path T 0 , … , T ℓ T_{0},\ldots,T\ell , we first use a MaxSAT solver to find the path of length ℓ \ell that minimizes the number of unit flips performed from T ℓ − 1 T_{\ell-1} to T ℓ T_{\ell} . The MaxSAT formulation is equal to the SAT formulation with soft clauses ¬ f ( u , v , u 2 , v 2 , ℓ ) \neg f(u,v,u_{2},v_{2},\ell) for each last step flip variable. We then find the path of length ℓ − 1 \ell-1 from T 0 T_{0} to the T ℓ − 1 T_{\ell-1} of the previosu path that minimizes the number of unit flips performed from T ℓ − 2 T_{\ell-2} to T ℓ − 1 T_{\ell-1} . We continue this way for r r steps. 4.3 Path Heuristic The SAT formulation finds the shortest path connecting two triangulations reasonably fast, but it may be too slow for some usages. We also designed a heuristic that produces reasonably short paths quickly. We are given two triangulations T 0 , T ′ T_{0},T^{\prime} and the goal is to find a short path from T 0 T_{0} to T ′ T^{\prime} . We use a greedy approach that iteratively obtains a triangulation T i + 1 T_{i+1} from a triangulation T i T_{i} as follows. Let F F denote the set of possible unit flips in T i T_{i} . More precisely, the elements of F F are pairs e , e ′ e,e^{\prime} of edges such that a unit flip from T i T_{i} removes e e and inserts e ′ e^{\prime} . We then build a graph G ( F ) G(F) with vertex set F F and edges between two unit flips that share a triangle. Notice that the possible parallel flips correspond to independent sets in G ( F ) G(F) . We assign a weight to the vertices as follows. The weight of a vertex e , e ′ e,e^{\prime} is the number of edges in T ′ T^{\prime} crossed by e ′ e^{\prime} minus the number of edges in T ′ T^{\prime} crossed by e e . Vertices of zero or negative weight are eliminated. We then proceed to greedily find an independent set I I in G ( F ) G(F) . We iteratively add to I I the unmarked vertex of maximum weight, breaking ties by minimum degree. We then mark all the vertices in the closed neighborhood of I I . We repeat until all vertices are marked. This iterative approach is repeated until we reach T ′ T^{\prime} , which will happen in O ( n 2 ) O(n^{2}) flips because of the following Theorem from [ 10 ] . Theorem 7 . Let T , T ′ T,T^{\prime} be two triangulations of the same point set. If T ≠ T ′ T\neq T^{\prime} , then there exists a unit flip that replaces an edge e ∈ T e\in T by an edge e ′ e^{\prime} such that e e crosses more edges of T ′ T^{\prime} than e ′ e^{\prime} does. We further improve the heuristic using the squeaky wheel paradigm [ 11 ] . Initially, we assign weight 1 1 to every edge. We modify the definition of the weight of a flip as follows. The weight of a flip e , e ′ e,e^{\prime} is the sum of the weights of the edges in T ′ T^{\prime} crossed by e ′ e^{\prime} minus the sum of the weights of the edges in T ′ T^{\prime} crossed by e e . When we reach triangulation T i + 1 = T ′ T_{i+1}=T^{\prime} from a triangulation T i T_{i} we increment the weight of all edges in T ′ T^{\prime} that are not in T i + 1 T_{i+1} . We repeat the greedy algorithm with the new weights, keeping the best solution found. This procedure is repeated multiple times. Journal: 4.4 Solution Heuristic We use the following strategy to obtain reasonably good initial solutions that we may use as a basis to improve with the aforementioned methods. We start by adding the Delaunay triangulation as a candidate center. We then build other candidate centers by performing flips starting from the Delaunay triangulation. Given an edge e e and a triangulation T T , let χ ( e , T ) \chi(e,T) denote the number of segments of T T crossed by e e . We repeatedly perform unit flips that remove an edge e e and add an edge e ′ e^{\prime} maximizing ∑ T ∈ 𝒯 χ ( e ) p − χ ( e ′ ) p , \sum_{T\in\mathcal{T}}\chi(e)^{p}-\chi(e^{\prime})^{p}, as long as the value of the sum is positive. We add the triangulation we obtained to the set of candidate center and repeat the process for a different value of p p . We calculate the paths from the candidate centers to each solution, building a solution pool. For the next step it will be useful to have a small number of unit-flips in the last flip of the path from the input triangulation to the center. To do that, we either use the greedy heuristic or a MaxSAT formulation. To improve the solution pool, we pick a solution from the pool and look at the triangulations that are one flip away from the center in each path. For each such triangulation, we compute the distance to the input triangulations and add the solution to the pool as before. Journal: In Section , we present the heuristics used to find solutions to the instances that we could not solve exactly. Journal: Greedy Greedy Squeaky Squeaky SAT SAT forward backward forward backward happy exact n n ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t ℓ \ell t 500 13 4.2 12 3.7 13 45 12 18 12 1512 12 10191 1000 12 7.8 12 6.8 12 25 12 38 11 6806 11 78264 1500 13 13 12 12 12 52 12 23 11 19302 11 201353 2000 15 21 13 18 13 65 13 104 13 16937 13 485177 3000 15 36 15 33 14 193 15 433 14 140729 ⋅ \cdot ⋅ \cdot 4000 18 57 16 51 16 577 15 655 15 101402 ⋅ \cdot ⋅ \cdot 5000 18 70 17 70 16 238 17 278 16 1037840 ⋅ \cdot ⋅ \cdot 6000 17 93 16 83 17 1071 16 644 16 271081 ⋅ \cdot ⋅ \cdot 7000 17 94 17 96 17 180 17 407 16 471389 ⋅ \cdot ⋅ \cdot Table 1: Length and computation time (in milliseconds) from the Delaunay triangulation to the first input triangulation of the rirs- n n - -20 instance for different values of the number of points n n . The columns respectively correspond to the greedy heuristic forward and backward, the squeaky wheel heuristic forward and backward, the SAT solution with the happy edges conjecture, and the SAT solution without the happy edges conjecture, unless it takes too long. Journal: The best lengths found are shown in bold. Journal: The best lengths found are shown in bold. Journal: In this section, we use the Delaunay triangulation as one extreme, because it is a well defined triangulation that makes a reasonably good (but not very good) center. Table shows the length of the path and the running time of different heuristics and SAT solutions with and without the happy edges conjecture. The paths are calculated from the Delaunay triangulation to the first input triangulation of several instances. The SAT paths are obtained by first running the squeaky wheel heuristic in both directions, and then iteratively decreasing the path length. Notice that the running time of the heuristics is much smaller, while the result is rarely more than 1 1 unit away from the optimal distance, especially if we take the minimum of both directions. We run the squeaky wheel heuristic for at most 16 16 iterations, but stop earlier if the length increases from one iteration to the next. Journal: We now present the exact solver that we used to solve most instances exactly. Journal: Notice that the impact of the happy edges conjecture is less significant than when computing only paths, as there are few common edges on all input triangulations. We remark that during the competition, we managed to find exact solutions to 189 189 of the 201 201 small instances without assuming the happy edges conjecture. Journal: 4.5 Crossing Lower Bound The heuristic that estimates b ( s ) b(s) for a string s s (see Section ) is surprisingly accurate. Figure shows the heuristic error rates for different string lengths. The smallest strings where the heuristic fails have length 12 12 and are: ⊲ ? ▼ ▲ ▲ ▼ ▲ ▲ ▲ ▲ ? ⊳ \triangleleft?\blacktriangledown\blacktriangle\blacktriangle\blacktriangledown\blacktriangle\blacktriangle\blacktriangle\blacktriangle?\triangleright , ⊲ ? ▲ ▼ ▼ ▲ ▼ ▼ ▼ ▼ ? ⊳ \triangleleft?\blacktriangle\blacktriangledown\blacktriangledown\blacktriangle\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown?\triangleright , ⊲ ? ▲ ▲ ▲ ▲ ▼ ▲ ▲ ▼ ? ⊳ \triangleleft?\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangledown\blacktriangle\blacktriangle\blacktriangledown?\triangleright , and ⊲ ? ▼ ▼ ▼ ▼ ▲ ▼ ▼ ▲ ? ⊳ \triangleleft?\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangle\blacktriangledown\blacktriangledown\blacktriangle?\triangleright , with the question marks replaced by ▼ \blacktriangledown or ▲ \blacktriangle , which gives an error rate of 4 ⋅ 4 / 2 10 ≈ 0.016 4\cdot 4/2^{10}\approx 0.016 as the two extreme symbols are fixed. We compare the error rate when the heuristic uses exact preprocessed values to solve subproblems and when the heuristic does not use any preprocessed data. The heuristic was never wrong by more than one unit on strings of up to 28 28 symbols. Figure 7: Error rate of the crossing lower bound for strings with k k symbols, which corresponds to k − 1 k-1 crossings. 4.6 Heuristic Solutions The typical process to solve instances that we did not solve exactly consists of several steps. First, we use the heuristic from Section to obtain a reasonably good center. Notice that no SAT solver is used in this part. The evolution of the objective value for this step is shown in Figure . The name of the rirs instances is composed of two values. The first is the number of points and the second is the number of input triangulations. Figure 8: Evolution of the best solution found by the heuristic solver without any SAT solver for different instances. Second, we build a new solution that keeps the same center but we recalculate the paths using the SAT formulation from 2.1 , assuming the happy edges conjecture (Section 2.5 ) and inexact lower bounds (Section ). This will typically reduce the objective value by 1 1 to 4 4 percent. The calculation of 50 50 paths in each solution is shown in Figure . Notice that the running time increases rapidly with the number of points and that finding a shorter path (satisfiable SAT problem) is typically slower than when no shorter path exists (unsatisfiable SAT problems). Figure 9: Path by path improvement of the heuristic solutions using a SAT solver, where each path is recalculated but the center is kept unchanged. Each black vertical bar represents the beginning of the computation of a path. Third, we improve the solution using the SAT formulation from Section 2.2 , assuming the happy edges conjecture (Section 2.5 ) and inexact lower bounds (Section ). This part requires adjusting a large number of parameters in order to obtain SAT problems that are not too hard. The parameters include the distance to the previous center, the distance to the previous path, and whether the solution will be trimmed. Optionally but recommended when the problem is trimmed, we use MaxSAT to reduce the number of unit flips close to the center. The improvement of some solutions over time is shown in Figure . Notice that there is a significant preprocessing time to calculate edge variables with a limited number of crossings. This preprocessing is applied initially and after every improvement. Also notice that unsatisfiable SAT problems, which mean no improvement in the solution, are solved much faster than satisfiable ones. Figure 10: Improvement of the whole solution using a SAT solver and reducing the length of a random path by one unit at a time. We constrain the edges in the new solution to cross at most 3 3 edges of the corresponding triangulation in the solution (except for the instance rirs-500-20 , where the slower but more effective execution with the parameter set to at most 7 7 edges is also pictured) but do not use trimming. Each black vertical bar represents a new path length that we try to decrement. Journal: 5 Conclusion and Open Problems We were surprised that we managed to solve so many instances exactly and how well an heuristic approximates the exact distance. We believe the following factors help explain the strong practical performance: • The short path length that allows a somewhat small number of variables. • A SAT model where most clauses have size 2 2 . • The ability to eliminate many variables through several arguments. • The fact that the happy edges conjecture is either true or at least holds in most practical cases. The short path lengths are somewhat surprising, given that an Ω ( n ) \Omega(n) lower bound is presented in [ 9 ] , in contrast to the Θ ( log n ) \Theta(\log n) bound for combinatorial triangulations [ 12 ] , where we are allowed to flip non-convex quadrilaterals. In the challenge instances, we observed path lengths that are roughly O ( log n ) O(\log n) . Still, there are random instances with only 160 160 points and 20 20 input triangulations and woc instances with only 185 185 points and 6 6 triangulations that we could not solve exactly. Also, we still managed to improve solutions to instances with as few as 320 320 points and 20 20 input triangulations months after the beginning of the challenge. The challenge instances did not have many points in convex position. Surprisingly, the case where all points are in convex position is the hardest for our SAT formulation, as there are Θ ( n 4 ) \Theta(n^{4}) empty convex quadrilaterals. We wonder if a different model works better when all and also when most points are in convex position. We believe that the same problem with unit flips is significantly harder because the long path lengths make the SAT formulation much more complex and removing a happy edge can reduce a path length from Θ ( n 2 ) \Theta(n^{2}) to Θ ( n ) \Theta(n) . Many theoretical open problems remain, such as proving Conjecture 3 . We also wonder if parallel flip distance problem is NP-hard in general and in convex position, as well as the unit flip distance problem in the convex case (the problem is NP-hard for general point sets [ 14 ] ). We also do not know if the problem of calculating b ( s ) b(s) (see Section ) can be solved in polynomial time, possibly using dynamic programming. by Guilherme D. da Fonseca, Fabien Feschet, Yan Gerard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21293.txt.
Introduction
Fonseca and co-authors describe how Team Shadoks won the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. Each instance gives several triangulations of one point set. The team had to pick a center triangulation and find short parallel-flip paths from each input to it, minimizing total path length. Their approach mixes exact SAT methods with greedy heuristics. SAT and MaxSAT also improve solutions after the fact. They present encodings for bounded length paths and a global form for fixed path length vectors, and report solver performance.
Catalog record
| CREATOR | Guilherme D. da Fonseca, Fabien Feschet, Yan Gerard |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47523 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21293
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shadoks Approach to Parallel Reconfiguration of Triangulations Journal: An instance is a collection of triangulations of a common point set. We must select a center triangulation and find short parallel-flip paths from each input triangulation to the center, minimizing the sum of path lengths. Journal: We present a SAT encoding for bounded-length paths and a global formulation for fixed path-length vectors. We discuss how these components interact in practice and summarize the performance of our solvers on the benchmark instances. Journal: and heuristics Journal: Nevertheless, we also developed heuristics that do not rely on any external solver, which are important to find initial solutions to large instances, which are then improved by roughly 10 % 10\% using SAT and MaxSAT solvers. Journal: We describe our exact algorithms in Section 2 , the heuristics in Section , and discuss the results we obtained in Section 3 . Concluding remarks and open problems are presented in Section . Journal: This section describes all elements of our exact solver, many of which are also used in the heuristic solvers. We first show how to use a SAT solver to compute shortest paths between two triangulations (Section 2.1 ). We then show how to extend this result to test if a solution with a list of path lengths exists (Section 2.2 ). We show how to obtain lower bounds in Section 2.3 and put the previous elements together to describe our exact solver in Section 2.4 . Journal: Notice that we can eliminate e ( u , v , 0 ) e(u,v,0) for u v ∉ T 0 uv\notin T_{0} and e ( u , v , ℓ ) e(u,v,\ell) for u v ∉ T ℓ uv\notin T_{\ell} . This is, however, only a special case of a more general rule. Journal: Proof. Consider the sequence L L of edges of T T crossed by s s in the order they cross the segment s s . A parallel flip cannot remove two consecutive edges of L L because they share a triangle, hence the theorem follows. ∎ Journal: We have the following theorem. Journal: Proof. Let d i , j d_{i,j} denote the distance between the input triangulations 𝐓 i , 𝐓 j \mathbf{T}_{i},\mathbf{T}_{j} . Let C C be a potential center and let r i r_{i} be the distance from C C to 𝐓 i \mathbf{T}_{i} . Consider a cycle 𝐓 1 , … , 𝐓 k \mathbf{T}_{1},\ldots,\mathbf{T}_{k} in the cycle packing. By triangle inequality d i , i + 1 ≤ r i + r i + 1 d_{i,i+1}\leq r_{i}+r_{i+1} with indices taken modulo k k (see Figure 3 (b)). Summing over the inequalities for i i from 1 1 to k k , we have that the length of the cycle is at most 2 ∑ i r i 2\sum_{i}r_{i} . Applying the same argument to every cycle, the theorem follows. ∎ Journal: 4 Heuristics In this section, we describe different approaches that can be used when we do not need to guarantee the optimality of the solution. In Section 2.5 , we present a conjecture that allows us to significantly increase the performance of the SAT solver. In Section , we show how to further increase the performance of the SAT solver using a heuristic coupled with some instance-independent preprocessed data. In Section , we show how to use the SAT solver to improve existing solutions. In Sections and , we respectively show how to compute short paths and good solutions without a SAT solver. Journal: Enforcing that an edge never disappears and later reappears along a path actually makes the SAT formulation harder to solve. However, there are some implications of the conjecture that are very useful to make the SAT formulation shorter and easier to solve. Journal: 4.1 Crossing Lower Bound Let b ( u v , T 0 ) b(uv,T_{0}) denote the number of parallel flips needed to obtain an edge u v uv starting at a triangulation T 0 T_{0} . Clearly, when creating the SAT formulation for a path T 0 , T 1 , … T_{0},T_{1},\ldots we only need to define the edge variable e ( u , v , i ) e(u,v,i) for i ≥ b ( T 0 , u v ) i\geq b(T_{0},uv) . Theorem 1 implies that if an edge u v uv crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} , then b ( u v , T 0 ) ≥ ⌈ log 2 ( χ ( u v , T 0 ) + 1 ) ⌉ b(uv,T_{0})\geq\lceil\log_{2}(\chi(uv,T_{0})+1)\rceil . This bound is tight when all the edges of T 0 T_{0} that cross u v uv share a common endpoint and the endpoints are in convex position (Figure ). However, there are different ways in which the edges of T 0 T_{0} may cross u v uv that may imply higher values of b ( u v , T 0 ) b(uv,T_{0}) . Figure 5: A path of length 3 3 to insert an edge that had 6 6 crossings. We consider estimations of b ( u v , T 0 ) b(uv,T_{0}) based on the sequence of triangles that contain an upper or a lower edge (Figure ). An edge u v uv that crosses χ ( u v , T 0 ) \chi(uv,T_{0}) segments of T 0 T_{0} is translated into a string s = s ( u v , T 0 ) s=s(uv,T_{0}) of χ ( u v , T 0 ) + 1 \chi(uv,T_{0})+1 symbols in the alphabet { ▼ , ▲ , ⊲ , ⊳ } \{\blacktriangledown,\blacktriangle,\triangleleft,\triangleright\} , according to which sides of u v uv contain the edges that are not crossed by u v uv in each triangle. Figure 6: A path of length 4 4 to insert an edge that had 6 6 crossings. Each triangle is labeled and colored as containing an upper or a lower edge. The unit flips on T 0 T_{0} have equivalent replacements on s s that replace the substring on the left-hand side by the substring on the right-hand side . We define a substring as a contiguous subsequence. Flipping the two extreme triangles translates to the extreme replacements ⊲ ▲ → ⊲ \triangleleft\blacktriangle\rightarrow\triangleleft , ⊲ ▼ → ⊲ \triangleleft\blacktriangledown\rightarrow\triangleleft , ▲ ⊳ → ⊳ \blacktriangle\triangleright\rightarrow\triangleright , and ▼ ⊳ → ⊳ \blacktriangledown\triangleright\rightarrow\triangleright . Flipping intermediate triangles with the same orientation translates to ▲ ▲ → ▲ \blacktriangle\blacktriangle\rightarrow\blacktriangle and ▼ ▼ → ▼ \blacktriangledown\blacktriangledown\rightarrow\blacktriangledown , while flipping intermediate triangles of different orientations translates to ▼ ▲ → ▲ ▼ \blacktriangledown\blacktriangle\rightarrow\blacktriangle\blacktriangledown and ▲ ▼ → ▼ ▲ \blacktriangle\blacktriangledown\rightarrow\blacktriangledown\blacktriangle . The last flip to insert the edge u v uv is ⊲ ⊳ → ∅ \triangleleft\triangleright\rightarrow\emptyset . There are other replacements that may increase the string length such as ▲ → ▲ ▲ \blacktriangle\rightarrow\blacktriangle\blacktriangle , which consist of exchanging the left-hand and right-hand side of some aforementioned