CG#Hunters Approach to Central Triangulation Under Parallel Flip Operations

An edge flip of a triangulation $T$ is an operation that removes a shared edge $e$ between two adjacent triangles forming a convex quadrilateral, and replaces it with the opposite diagonal of the quadrilateral. Given two triangulations $T_1$, $T_2$ on the same point set $P$, there exists a flip path from $T_1$ to $T_2$, which is a sequence of flips applied to $T_1$ to make $T_2$. There has been a fair amount of work on computing flip paths between two triangulations [2, 3, 5, 6], and it is known to be NP-complete to compute a shortest one [7].

Taking a step further, the CG:SHOP 2026 Challenge considers a parallel flip operation, which is a set of multiple edge flips that can be performed simultaneously because they do not share any triangles. We call a sequence of parallel flips a parallel flip path. In the problem, we are given a set of triangulations on the same point set and the goal is to compute a central triangulation on the same point set while minimizing the sum of the lengths of parallel flip paths from each triangulation. The problem is formally defined as follows.

There were 250 instances of three types (random-, woc-, and rirs-) given. For more details on the instances, see the survey paper [1].

First, we introduce our initial algorithm for computing an initial solution for each instance. Given an instance $I=(P,𝒯)$, our algorithm runs while maintaining a (multi)-set of triangulations $\widehat{𝒯}$, starting with $\widehat{𝒯}=𝒯$. At each step, it selects one triangulation in $𝒯$ and applies a parallel flip to reduce the total number of intersections among the triangulations $\mathrm{cr}(\widehat{𝒯})$. The algorithm terminates when $\mathrm{cr}(\widehat{𝒯})$ becomes zero, which implies that the triangulations in $\widehat{𝒯}$ are the same. Then the algorithm returns the triangulation as the central triangulation $C$.

In doing so, we first use the following observation from [3].

Lemma 2 implies that we can always find a parallel flip from a triangulation $T\in \widehat{𝒯}$ that reduces the total number of intersections when $|\widehat{𝒯}|=2$. To use this observation for an instance with $|𝒯|>2$, we claim the following stronger argument.

We presume that Conjecture 3 holds to design our algorithm, and so far during the contest, we have not encountered any counterexample. Using Conjecture 3, a single step of our algorithm works as follows. For each flippable edge $e$ in each triangulation $T\in \widehat{𝒯}$, let $e^{\prime }$ be the edge obtained by flipping $e$ in $T$. Then we define a score for $e$ as the change in $\mathrm{cr}(\widehat{𝒯})$ after flipping $e$, that is, ${\sum }_{T^{\prime }\in \widehat{𝒯}\setminus \{T\}}(\mathrm{cr}(e,T^{\prime })-\mathrm{cr}(e^{\prime },T^{\prime }))$ and compute it. Observe that there is at least one positive-scored edge if Conjecture 3 holds.

After computing the scores of the edges, we compute a possible parallel flip to reduce $\mathrm{cr}(\widehat{𝒯})$ for each $T\in \widehat{𝒯}$. Within $T$, the edges to flip are chosen in a greedy manner. First, our algorithm sorts the positive-scored edges in $T$ in descending order of their scores. Then, it scans through the sorted edges and picks an edge if it is independent of the already picked edges. After scanning, the algorithm chooses a triangulation with a possible parallel flip that reduces $\mathrm{cr}(\widehat{𝒯})$ the most and applies the parallel flip. Then the algorithm proceeds to the next step. See Figure 1.

By tracking the parallel flips applied to the triangulations during the algorithm, we can also obtain a parallel flip path $\pi (T,C)$ for each $T\in 𝒯$. We mainly used this algorithm for obtaining initial solutions. However, this approach requires high computational cost. To address this, we also used a representative-set-based approach, which is described in Section 4.

In this section, we address our two optimization approaches to improve our solutions: recomputing the paths and finding a new central triangulation.

Additionally, to reduce the computational cost of the finding central triangulation $C$, we utilize a weighted representative-set-based approach. This method is motivated by the concept of $1$-median coresets [4], leveraging the fact that the parallel flip distance satisfies the triangle inequality. By discretizing the metric space, we construct a compact surrogate set ${𝒯}_{\mathrm{rep}}$ that preserves the properties of the objective function while significantly reducing the number of triangulations to be processed.

The construction of ${𝒯}_{\mathrm{rep}}$ is executed through a two-stage distance-based partitioning process. First, if a central triangulation $C$ from an initial solution is available, we set the anchor triangulation $A$ as $C$; otherwise, we choose $A$ as a random triangulation $T\in 𝒯$. For each triangulation $T_i\in 𝒯$, we compute $\pi (T_i,A)$ and the distance ${\delta }_i≔|\pi (T_i,A)|$. We establish exponentially growing intervals that double in size based on the baseline scale $R≔{\sum }_i{\delta }_i/|𝒯|$, and then partition $𝒯$ by grouping each triangulation $T_i$ according to which interval its distance ${\delta }_i$ falls into. Next, we refine these partitions by sorting the triangulations by ${\delta }_i$ within each interval and further subdividing them into $1/\epsilon$ subsets according to the granularity parameter $\epsilon \in (0,1)$. Finally, from each refined subset, we select a random triangulation and add it to ${𝒯}_{\mathrm{rep}}$. We assign its weight $w(T)$ equal to the size of that subset, ensuring the total sum of weights equals the original size $|𝒯|$. See Figure 4.

The effectiveness and accuracy of this approach are summarized in Table 1. As shown, the proposed method substantially reduces the number of triangulations $|𝒯|$ – especially for large instances – while yielding objective values closely approximating the solutions derived from the whole triangulation set.

In the following, we present a few observations about our approaches.

• $\mathrm{■}$

  When comparing the total parallel flip distance of rirs- instance and the three instances between top teams, we were in second place. See Table 2.

• $\mathrm{■}$

  To understand above results, we compared the initial algorithm and various optimizations. For rirs- instances, the initial algorithm produced sufficiently short paths. For other instances, however, the path optimizations in Section 3.1 significantly reduced the distances in most cases. See Figure 5.

• $\mathrm{■}$

  For some rirs- instances, the large scale neighborhood search in Section 3.2 repeatedly generated the same central triangulation (i.e. $C=C^{\prime }$ in Figure 3), regardless of the randomly selected $M_T$’s. Nevertheless, the parallel flip paths were consistently shorter.