Source-linked AI summary
Closure complexity of longest-edge bisection for triangular meshes
Yuwen Li, Zhiyuan Yang
TL;DR
Geometric longest-edge bisection lacks a direct cumulative closure analysis because its refinement edges are recomputed from geometry, and a fine mark can force refinement of a coarser triangle. The paper analyzes a serial terminal-priority propagation rule and proves a cumulative closure estimate using single-mark locality and charging.
Problem
For geometric longest-edge bisection, refinement edges are recomputed after each step, so existing closure analyses based on inherited reference-edge data do not transfer directly.
Source: §1 · p. 2Method
The proof establishes single-mark locality for terminal-priority serial LEPP refinement and uses a charging argument to derive the cumulative estimate.
Source: §1 · p. 2, §3.3 · p. 8, §4 · pp. 9, 11Results
Theorem 1.1 establishes the first cumulative closure estimate for geometric longest-edge bisection under the stated LEPP rule.
Source: §1 · pp. 2–3Takeaways & Limitations
The result supplies a cumulative closure estimate for geometric longest-edge bisection under the specified serial rule.
Source: §1 · pp. 2–3The analysis assumes a finite conforming initial mesh of a bounded polygonal domain in R2 and considers meshes obtainable by finitely many longest-edge bisections.
Source: §2.1 · p. 3, §3.3 · p. 8
Abstract
from arXiv · showhide
On triangular meshes, we analyze local mesh refinement based on longest-edge bisection equipped with the serial longest-edge propagation-path closure. Ties are resolved by terminal priority: if the incoming shared edge is a longest edge of the neighboring triangle, the pair is declared terminal and that edge is bisected. For every adaptive mesh sequence $\mathcal{T}_0, \mathcal{T}_1, \ldots, \mathcal{T}_L$ with a sequence of marked sets $\mathcal{M}_0, \mathcal{M}_1, \ldots, \mathcal{M}_{L-1}$, we prove the cumulative closure estimate $$\#\mathcal{T}_L-\#\mathcal{T}_0 \lesssim\sum_{\ell=0}^{L-1}\#\mathcal{M}_\ell.$$ The proof derives single-mark locality from the uniform multiplicative gap between possible descendant diameters implied by finite similarity classes, and converts this locality into the cumulative estimate through a Binev--Dahmen--DeVore-type charging argument.
1. Introduction
The paper addresses the lack of a direct closure analysis for geometric longest-edge bisection, where refinement edges are recomputed from triangle geometry. It proves a cumulative closure estimate for a specified serial propagation rule, using single-mark locality and a charging argument.
1. Introduction
- The refinement step must preserve conformity and uniformly nondegenerate elements while preventing conformity-only refinements from overwhelming marked elements.This balance is presented as a requirement for retaining adaptivity’s computational advantage.Source: §1 · p. 1
- Geometric LEB lacks inherited reference-edge data: its bisection edge is recomputed after each refinement, so closure analyses for other bisection rules do not transfer directly.A Binev–Dahmen–DeVore theorem for LEB was posed as an open problem in [4].Source: §1 · p. 2
- A fine mark can force refinement of a substantially coarser triangle, so a packing argument centered only on the mark may undercharge that refinement.The proof must also account for earlier marked triangles without an inherited reference edge.Source: §1 · p. 2
- The analyzed rule uses terminal priority: when the incoming shared edge is also longest in the neighboring triangle, the path stops and bisects that edge.The diameter strictly increases at every nonterminal step.Source: §1 · p. 2
- The proof derives scale-sensitive locality for triangles created by one mark from the uniform diameter gap implied by finite similarity classes.It then sums the locality bounds over marks and new triangles.Source: §1 · p. 2
- Theorem 1.1 gives the first cumulative closure estimate for geometric longest-edge bisection under the stated LEPP rule.Its constant may depend on the fixed initial mesh, rather than only on its minimum angle.Source: §1 · pp. 2–3
2. Preliminaries
The preliminaries specify conforming triangular meshes, longest-edge bisection, and generations, then define a terminal-priority propagation path and its serial refinement rule.
2.1. Conforming meshes and bisection generations.
- A conforming mesh consists of nondegenerate triangles with disjoint interiors that meet only at a common vertex or a complete common edge.The domain is bounded and polygonal, and hanging nodes are excluded.Source: §2.1 · p. 3
- Longest-edge bisection joins the midpoint of a longest edge to the opposite vertex, producing two children of equal area.The children are [v0, m, v2] and [m, v1, v2] when the bisected edge is [v0, v1].Source: §2.1 · p. 3, Figure 1 · p. 3
- A descendant’s generation counts successive bisections from its unique containing triangle in the initial mesh.Each triangle also has a longest-edge diameter and a barycenter.Source: §2.1 · pp. 3–4
2.2. Propagation paths and terminal priority.
- A terminal-priority LEPP follows longest edges until reaching a boundary edge or an interior edge that is longest in both adjacent triangles.In the latter case, the two adjacent triangles form the terminal pair; otherwise, the path advances to the neighboring triangle.Source: §2.2 · p. 4
- Single-mark refinement bisects the terminal edge in its one boundary-adjacent triangle or simultaneously in both triangles sharing an interior terminal edge.No other old edge is subdivided, so intermediate meshes remain conforming.Source: §2.2 · p. 5
- TP-LEB skips marks already bisected by earlier calls, and its estimates are uniform over permitted longest-edge choices and fixed serial mark orders.Termination of single-mark refinement is established in Theorem 3.7.Source: §2.2 · p. 5
3. Geometric structure and single-mark locality
Finite similarity classes yield a uniform multiplicative gap between possible descendant diameters. This gap controls growth and reach along LEPPs, supporting generation and spatial locality for a single mark and termination of its refinement call.
3.1. Finite similarity classes and diameter scales.
- Finite similarity classes of longest-edge descendants imply a uniform multiplicative gap between distinct possible diameters.The gap is stronger than shape regularity and supplies the scale separation used in the subsequent path estimates.Source: §3.1 · p. 6
3.2. Geometric growth along a LEPP.
- The diameter increases strictly at every nonterminal LEPP step, yielding geometric growth and a bound on the reach of each propagation path.The path estimate applies to every triangle in the terminal set relative to the starting mark.Source: §3.2 · p. 7
3.3. Generation and spatial locality for one mark.
- Single-mark locality bounds the generations and spatial distance of triangles created during each refinement iteration, with constants depending only on T0.The locality bound limits the generations that can occur during the call; together with finiteness of the initial mesh, this yields termination and a conforming refinement in which the marked triangle is bisected.Source: §3.3 · p. 8
4. The cumulative charging argument
The cumulative argument charges newly created triangles to marks, bounds the charge from each mark, and aggregates those bounds to obtain the closure estimate.
4. The cumulative charging argument
- A triangle receives charge from a mark only when their barycenters are within E times 2^-gen(T)/2.At a fixed generation, the number of triangles in such a neighborhood is bounded using packing and triangle-area estimates.Source: §4 · p. 9
- Each mark has uniformly bounded total charge, with the bound depending only on the initial mesh and refinement rule.The one-mark argument uses a bound on the generations of triangles that can receive charge and packing at each generation.Source: §4 · pp. 9–10
- Tracing a triangle's creation back through earlier calls links it to distinct marks, providing the chain used in the cumulative charge bound.The trace ends at an initial-mesh triangle, with each intervening mark belonging to a different call.Source: §4 · p. 10
- The geometric argument handles both barycenter paths that remain in B and paths that first leave B at an intermediate index.Figure 3 illustrates the two cases used in Theorem 4.4.Source: §4 · pp. 10–11, Figure 3 · p. 11
- The total number of new triangles is bounded by a constant times the total number of marked triangles across the adaptive sequence.The proof combines Propositions 4.3 and 4.4 to obtain the cumulative estimate.Source: §4 · p. 11
5. Numerical experiments
The West Lake experiments compare TP-LEB with newest-vertex bisection and red–green refinement under a common element bound. TP-LEB has the smallest final shape ratio in this test, and its later-range residual estimators are smaller at comparable element counts.
5. Numerical experiments
- The test uses West Lake's main connected water component, retaining island and causeway boundaries but omitting a separate pond; the initial mesh has 2,333 triangles.The initial mesh was generated with Gmsh's Frontal–Delaunay algorithm.Source: §5.1 · p. 12
5.1. Experimental setting.
- The experiments use continuous piecewise affine finite elements with Dirichlet conditions on every boundary component, and report estimator reduction without an exact solution.The residual estimator includes interior-edge jump terms.Source: §5.1 · p. 12
- All methods start from the same mesh and refine largest-indicator elements until the largest mesh level within the 40,000-element bound.Each method uses its own current solution and indicators; TP-LEB, NVB, and RG use their specified refinement procedures.Source: §5.1 · p. 12
5.2. Estimator reduction and shape quality.
- TP-LEB and NVB have close cumulative growth ratios, RG has a larger ratio, and TP-LEB has the smallest final shape ratio in the West Lake test.Table 1 reports results at the 40,000-element bound.Source: §5.2 · p. 13, Table 1 · p. 14
- In the later sampled mesh range, TP-LEB has smaller residual estimators than NVB and RG at comparable element counts.Figure 4 plots estimator ratio against element count; final values correspond to different meshes, while curves compare their common element range.Source: §5.2 · pp. 13–14, Figure 4 · p. 13