A reinforcement learning agent produced all-quadrilateral meshes on all 96 held-out domains, reaching the provable irregularity floor on 90

The authors propose using the vertex-irregularity lower bound par, derived from the discrete Gauss–Bonnet identity, as the optimality criterion for quadrilateral block decomposition, and show it is fixed by the domain's corner angles and topology alone and can be computed once before any mesh exists. Block decompositions have largely been built by hand or by heuristics that do not target optimality; here the bound due to Peng and Wonka and Peng et al. becomes the termination criterion of an MDP, so every success carries a certificate of optimality. The paper states Theorem 1 with a triangle-inequality proof and proves the discrete Gauss–Bonnet lemma in Appendix A; par is computed before meshing begins, and a decomposition reaching it is provably optimal in its connectivity.

The authors design an action space of four local edits acting directly on the half-edge (DCEL) data structure, plus a policy network whose convolutions follow the next/previous/twin pointers, so one checkpoint applies unchanged to domains larger than any seen in training. Unlike Narayanan et al., whose moves take one all-quadrilateral mesh toward ideal vertex degrees, this agent starts from the bare boundary, targets a bound computed from the domain, includes element quality in its reward, and overcomes the sparse reward by cloning. No parameter is indexed by template position or mesh size; in the Appendix J ablation a Transformer encoder with the same parameter count, features, action space and budget reaches par on about half as many domains as the convolution.

The authors cross the sparse-reward barrier by behaviour cloning: starting from trivially constructible optimal meshes such as polyominoes and walking backward to a single face yields move-by-move solutions in the agent's own action space, after which PPO continues training. Uniform random play reaches par on about three percent of five- and six-sided polygons and on none with more than eight sides, and PPO from a random initialisation reaches it on about one percent of domains after a million steps; cloning followed by PPO raises this substantially. Cloning uses about k (observation, optimal move) pairs for six epochs, reaching top-one agreement with the certified sets; PPO then runs four million steps on a mixture of generated and certified domains, with the whole recipe taking about four hours on a laptop (Apple M2, eight cores).

On 96 held-out domains the agent produces an all-quadrilateral mesh on every one, a usable one on 95.7 on average and a provably optimal one on 90; on 64 domains twice the training size it completes all, is usable on 62, and keeps a median excess over par below one against Gmsh's 39 at the same element count. Gmsh's strongest configuration at the same element count completes 51, is usable on 38 and optimal on none, and even at three to fourteen times the elements never produces a more regular mesh; across all seven configurations the certified optimum is reached three times in attempts. Each domain is attempted five times (one greedy, four sampled) at a doubled move budget, every all-quadrilateral state is untangled by the same smoother and ranked by all-quadrilateral first, then minimum quality, then closeness to par; reported counts are means over six rollout seeds in distribution and four on the larger set.

The result concerns coarse quadrilateral block decomposition of planar polygonal domains, including holes and curved boundaries, and applies to structured, multi-block discretisation and subdivision pipelines that need regular connectivity; the authors release geo2d as a benchmark generator and scoring protocol, along with the environment, network, checkpoint and scoring scripts, so each evaluation domain is reproduced exactly by a preset and a seed. The same checkpoint applies unchanged to larger boundaries (up to twice the training size) and to curved boundaries, where it is paired with a test-time repair search.

Several table values appear as blank cells in the loaded text, so usable rates, excess over par and at-par proportions can only be cited from the numbers stated in the abstract and prose; on curved boundaries the quality conclusion depends on whether corner quality is measured against the arc tangent or the chord, and the two metrics give noticeably different usable rates, both of which the authors report. Training-seed spread on the larger set is about five domains, above the evaluation-seed spread, so those numbers are best read as ranges. The solved test relies on an untangling smoother, and the authors note that an agent drawing well-shaped meshes without one would be preferable.