PaperlayerView exact revision on arXiv

Source-linked AI summary

A Lloyd-stabilized Voronoi particle method

Bruno Després, Borjan Geshkovski

arXiv:2609.28135v1math.NAcs.NA

TL;DR

Lagrangian Voronoï methods can suffer mesh degeneration as particles cluster, while the usual remedy rezones the mesh and remaps the solution. This paper analyzes centroid-directed Lloyd correction and shows that relaxation up to O(h^-1/2) retains Wasserstein consistency at O(h^1/4), without the usual remeshing.

  • Problem

    Lagrangian Voronoï methods can suffer mesh degeneration when particles approach one another and cells collapse, and the usual ALE remedy rezones and remaps the solution.

    Source: §1 · p. 1

  • Method

    The method adds a feedback-controlled Lloyd correction that moves particles toward cell centroids after the physical transport step.

    Source: §1 · p. 1, §1.4 · p. 5

  • Results

    With relaxation up to O(h^-1/2), the Wasserstein distance is bounded by C M h^1/4 for h ≤ 1.

    Source: §1.4 · p. 5, §4 · p. 17

  • Takeaways & Limitations

    The correction can regularize the mesh while retaining consistency, without the remeshing usually used in Lagrangian methods.

    Source: §1 · p. 1, §1.4 · p. 5

    Whether Laguerre cells yield improved theoretical or numerical conclusions for strongly inhomogeneous densities remains an open avenue.

    Source: §7 · p. 19

Abstract

from arXiv · show

We study the stability and consistency of Lloyd's algorithm used in combination with the Lagrangian transport of a density on a Vorono\"i tessellation. We show that relaxation rates as strong as $O(h^{-1/2})$, where $h$ is the mesh size, give convergence to the continuity equation in Wasserstein distance at the rate $O(h^{1/4})$. Thus the mesh can be kept regular by the correction alone, without the remeshing that Lagrangian methods usually require. An application is proposed for the compressible Euler equations.

1 Introduction

Lagrangian Voronoï methods move particle-generated tessellations with the fluid, but particle clustering can collapse cells. The paper studies centroid-directed Lloyd correction as a mesh stabilizer, analyzing its geometric effects and consistency with fluid transport.

1.1 Moving Voronoï tessellations

  • The method transports density on a moving Voronoï mesh generated by particles, with each cell carrying a fixed conserved mass.Particles move under physical velocities, which in numerical applications may be computed by a Riemann solver.Source: §1 · p. 1, §1.1 · p. 2

1 Introduction

  • The analysis seeks mesh stabilization and consistency conditions using geometric indicators that include quantization energy, a semi-discrete optimal-transport cost.The introduction notes that related transport costs have served as pressure rather than as a stabilizer in other Lagrangian schemes.Source: §1 · p. 1

1.2 Stabilizing (1.2) with Lloyd’s algorithm

  • One Lloyd step moves each particle toward its cell centroid to mitigate instabilities associated with tessellation displacement and Lagrangian density transport.The paper's vortex example contrasts collapsed cells without correction with a mesh close to a centroidal Voronoï tessellation with correction.Source: §1.2 · p. 3, Figure 1.1 · p. 3

1.3 Continuous-time viewpoint

  • In one dimension, the Lloyd correction acts as a discrete diffusion: it damps spacing-scale oscillations faster than modes of fixed physical wavelength.For αh = h^-1, the passage gives decay rates O(h^-1) for spacing-scale oscillations and O(h) for fixed-wavelength modes.Source: §1.3 · p. 4

1.4 Our contributions

  • Feedback relaxation up to O(h^-1/2) preserves consistency in Wasserstein distance at a rate not worse than O(h^1/4), while supporting mesh regularization without remeshing.The paper also proves quasi-uniformity for a feedback choice and illustrates Lloyd stabilization on compressible Euler equations.Source: §1.4 · p. 5

2 Convergence of the Voronoï histogram

This section establishes a criterion for weak consistency of the Voronoï histogram with the continuity equation. It compares the histogram and the equation's solution in Wasserstein distance, using transported measures to control their difference.

2 Convergence of the Voronoï histogram

  • The target is the weak solution of the continuity equation, represented by transporting its initial measure along the velocity flow.The section assumes a nonnegative L1 initial density and a velocity field Lipschitz in space.Source: §2 · p. 5
  • The proof compares the histogram with the exact solution through a coupling of the particle measure and the transported exact measure.The coupling is pushed forward along the particle trajectories and the flow of the velocity field.Source: §2 · pp. 6–7
  • If the initial and time-uniform Wasserstein distances between the discrete and exact measures tend to zero, the Voronoï histogram is weakly consistent with the continuity equation.The cited criterion uses W1(µh(0), µ(0)) + sup_t W1(µh(t), µ(t)) → 0.Source: §2 · p. 8

3 Persistence of quasi-uniformity

A nonnegative Lloyd feedback can keep configurations near the minimizers of F, preserving quasi-uniformity under the section’s assumptions. The resulting estimates control cell volumes but are not sufficient to establish convergence.

3 Persistence of quasi-uniformity

  • The result assumes a nonempty compact minimizer set, a quasi-uniform neighborhood U_r, and a Lipschitz velocity satisfying the stated boundary condition.Source: §3 · p. 9
  • If the initial configuration lies in U_r with energy gap below δ_r, a nonnegative feedback can keep it in U_r throughout [0, T], yielding D(X(t)) ≤ C1h.The feedback is chosen so the configuration remains near the minimizer set of F.Source: §3 · pp. 8–9
  • The feedback’s estimates control cell volumes but do not establish convergence, because the needed bound on accumulated correction A_h is unavailable.The text says B_h(T) would vanish if A_h = o(h^-min{p,2}), but gives no such bound for this feedback.Source: §3 · p. 14

4 A more general feedback which retains consistency

The section establishes that a broad class of Lloyd feedbacks preserves consistency, with convergence in Wasserstein distance at rate O(h^1/4). The feedback may be strong, while its energy and correction bounds control mesh quality.

4 A more general feedback which retains consistency

  • The energy may grow under deformation by the velocity field but remains O(h^2); dissipation controls centroid displacements and the total correction.The paper identifies the integral of α_hG as controlling both quantities.Source: §4 · p. 14
  • For feedback α_h that is locally Lipschitz on the open set of configurations with pairwise distinct generators, the stated bound is 0 ≤ α_h(X) ≤ G(X)/h^(5/2).Source: §4 · p. 14
  • Under the feedback assumptions, the particle solution exists on [0,T], generators remain distinct, and α_h stays nonnegative and bounded for each fixed h.The existence result states that the bound may depend on h.Source: §4 · pp. 14–15
  • For locally Lipschitz feedbacks with 0 ≤ α_h(X) ≤ G(X)/h^5/2, the Voronoï histogram converges uniformly in time in Wasserstein distance at rate O(h^1/4).The bound applies for h ≤ 1.Source: §4 · pp. 14, 15, 17
  • The critical estimate is available for any Voronoï tessellation, not specifically Lloyd dynamics, so the authors expect it to be suboptimal.The remark identifies this generic estimate as the proof bottleneck.Source: §4 · p. 18

5 One-sided Lipschitz velocities

The analysis extends to one-sided Lipschitz velocities, for which compression is unrestricted and generator separation may fail. Smoothing the velocity recovers the stated O(h^1/4) convergence rate.

5 One-sided Lipschitz velocities

  • The one-sided Lipschitz condition bounds expansion but permits compression, and it preserves uniqueness of the forward flow, including in the Filippov sense when velocity jumps.The transport solution is defined by carrying the initial measure along that flow.Source: §5 · p. 18
  • Unlike the Lipschitz-velocity setting, one-sided Lipschitz control does not ensure generator separation, and collisions can occur; the authors smooth the velocity to address this.The paper gives an example with colliding generators and applies the theorem to smoothed velocities.Source: §5 · p. 18
  • Choosing ε(h)=h for the smoothed velocity retains the convergence rate O(h^1/4).The convergence estimate for the smoothed velocities has constants independent of ε.Source: §5 · p. 18

6 A numerical illustration

A compressible Euler Riemann problem illustrates Lloyd correction on a shock-containing flow. The correction keeps generators separated and preserves the plotted wave positions, though a wall-heating error remains at the contact.

6 A numerical illustration

  • The test is a Riemann problem with a velocity jump across the shock, so it lies outside Theorem 2.1's hypotheses and is illustrative rather than covered by the convergence theorem.The strong gradients also trigger particles to approach extremely closely; Lloyd's algorithm acts as an additional repulsive force.Source: §6 · p. 19
  • With Lloyd correction, generators remain separated and the computation reaches t≈0.16 without noticeable instability, unlike the uncorrected run.Without correction, close generators make the final Voronoï construction unstable.Source: §6 · p. 19
  • The shock, contact, and rarefaction appear at the correct positions; the remaining visible discrepancy is wall heating at the contact, especially in density.Pressure, velocity, and density are compared with a fine-mesh reference solution.Source: §6 · p. 19
  • In the run with different adiabatic exponents, each value stays on its own side of the contact discontinuity, which the cited ALE methods cannot ensure.The compared exponents are γ_L=1.4 and γ_R=5/3.Source: §6 · p. 19

7 Outlook

The outlook identifies Laguerre cells, alternative centroid-based repulsions, and BV velocities as directions for further study. The proposed extensions remain questions to investigate.

7 Outlook

  • Laguerre cells may provide improved conclusions; particle weights could help follow strongly inhomogeneous densities while preserving the semi-discrete transport structure.The authors describe this as an avenue to explore, not an established result.Source: §7 · p. 19
  • The centroid is one repulsion choice associated with energy F; related energies also arise in Transformer mean-field models, where attention-kernel geometry determines token clustering [1] [18].Source: §7 · p. 21
  • How to extend the results to BV velocities, and what consistency cost that entails, remains open.Source: §7 · p. 21

A An envelope theorem for the gradient

For configurations with distinct generators, the appendix establishes differentiability of the energy and explains its gradient through the almost-everywhere unique nearest generator. The regularity argument also covers periodic domains.

A An envelope theorem for the gradient

B Complements on one-sided Lipschitz velocities

The appendix supplements the one-sided Lipschitz analysis with a face-based estimate and a mollification argument. It also shows that Lloyd repulsion alone does not guarantee particle separation.

B Complements on one-sided Lipschitz velocities

  • The one-sided velocity inequality bounds each face contribution, and the divergence theorem converts the weighted face integrals into the energy estimate for T_v.Source: B Complements on one-sided Lipschitz… · pp. 22–23
  • Lloyd repulsion alone does not prevent collisions: a compressive one-sided Lipschitz velocity can drive two generators together in finite time.In the example, the separation argument used in Theorem 4.1 relies on a lower bound that the one-sided condition does not provide.Source: B Complements on one-sided Lipschitz… · p. 23
  • Spatial mollification preserves the one-sided constant and yields a flow whose Wasserstein distance from the original flow is bounded by C‖ρ0‖_L1 ε^1/2.The energy and transport bounds are uniform in ε; the Lipschitz constant of the mollified velocity is used to produce the separated-generator solution.Source: B Complements on one-sided Lipschitz… · pp. 23–24
Loading 2609.28135v1…