Source-linked AI summary
Continuum Percolation Thresholds in Two Dimensions
Stephan Mertens, Cristopher Moore
TL;DR
The paper addresses how to compute percolation thresholds accurately in continuum models, whose objects have real-valued positions, orientations, and shapes. It adapts the union-find approach with additional data structures and finds precise thresholds for several two-dimensional models, while confirming conformal-field-theory predictions and essentially linear computational scaling.
Problem
Continuum percolation requires accurate threshold estimates for models with real-valued object positions and orientations, while threshold locations depend on object shape.
Method
The paper adapts the union-find algorithm with additional data structures, using microcanonical wrapping probabilities and Poisson convolution to analyze continuum percolation.
Results
The method produces threshold estimates several orders of magnitude more accurate than previous results and confirms conformal-field-theory predictions for finite-size scaling and wrapping probabilities.
Takeaways & Limitations
Continuum percolation thresholds for disks, squares, and sticks can be computed with an essentially linear-time union-find approach while exhibiting the predicted two-dimensional universality behavior.
Abstract
from arXiv · showhide
A wide variety of methods have been used to compute percolation thresholds. In lattice percolation, the most powerful of these methods consists of microcanonical simulations using the union-find algorithm to efficiently determine the connected clusters, and (in two dimensions) using exact values from conformal field theory for the probability, at the phase transition, that various kinds of wrapping clusters exist on the torus. We apply this approach to percolation in continuum models, finding overlaps between objects with real-valued positions and orientations. In particular, we find precise values of the percolation transition for disks, squares, rotated squares, and rotated sticks in two dimensions, and confirm that these transitions behave as conformal field theory predicts. The running time and memory use of our algorithm are essentially linear as a function of the number of objects at criticality.
I. INTRODUCTION
The paper adapts an efficient lattice-percolation strategy to continuum models, where threshold locations depend on object shape despite shared universality. It studies two-dimensional disks, squares, and sticks, obtaining accurate thresholds and tests of conformal-field-theory predictions.
- Continuum percolation models natural disordered systems, but their non-universal threshold locations must be studied separately from lattice models.
- The algorithm extends union-find methods to arbitrary-shaped continuum objects with real-valued positions and orientations.The study focuses on disks, aligned or randomly rotated squares, and randomly rotated sticks.
- The study extends previous threshold accuracy by several orders of magnitude and confirms predicted wrapping-cluster behavior and critical scaling.The reported results are consistent with rigorous bounds and conformal-field-theory predictions.
- Periodic boundary conditions track clusters wrapping horizontally, vertically, or in both directions, which have better finite-size effects than open-boundary crossings.
- The critical filling factor depends on object shape, with separate values defined for disks, aligned squares, rotated squares, and rotated sticks.For sticks, the filling-factor area is defined as a^ = l^2.
II. THE ALGORITHM
The algorithm adapts union-find to continuum percolation by efficiently finding overlaps, tracking clusters on a torus, and detecting wrapping through displacement vectors.
- Cluster tracking: Union-find tracks connected components as objects are added, using find(i) to identify representatives and merge(i, j) to combine clusters.The simulation adds objects one at a time and stops when a percolating cluster appears.
- Union-find optimization: Path compression links objects directly to their representatives, while path splitting links each object to its grandparent in one pass.Both approaches reduce future path lengths; path splitting has amortized cost O(α(n)).
- Union-find optimization: The amortized cost of find and merge is proportional to α(n), making total processing time essentially O(n).Here α is the inverse Ackermann function, which grows extraordinarily slowly.
- Continuum overlap detection: Square spatial bins restrict disk-overlap checks to the object’s own bin and its eight neighboring bins.With bin width equal to the disk diameter, this makes overlap searches constant-time on average.
- Wrapping detection: Periodic boundary conditions improve finite-size scaling, so the algorithm detects clusters that wrap horizontally or vertically around the torus.Wrapping is identified by comparing displacement vectors accumulated along alternative paths through a cluster.
- Performance: The complete algorithm runs essentially linearly in the number of objects at criticality, or equivalently in L^2.Its time includes adding objects until a wrapping cluster appears and summing displacement vectors along union-find paths.
III. ANALYSIS AND RESULTS
The analysis estimates continuum percolation thresholds by converting microcanonical wrapping data into grand-canonical probabilities and comparing finite-size behavior with conformal-field-theory predictions. For disks, the wrapping curves converge rapidly, their critical slope scales as L^3/4, and extrapolation uses an L^-11/4 correction.
- Wrapping probabilities: Microcanonical estimates of wrapping probabilities are convolved with Poisson weights to obtain grand-canonical functions R_L(η) for several wrapping types.The method evaluates any, horizontal, both-direction, and horizontal-only wrapping probabilities using winding numbers.
- Disk results: For disk percolation, R_L(η) curves for increasing L cross the exact critical wrapping probability, and the resulting η_L values rapidly converge to η_c.The crossings provide finite-size estimates of the critical filling factor used in the extrapolation.
- Finite-size scaling: The critical slope scales as 0.361L^3/4, confirming the universal two-dimensional exponent ν = 4/3 for finite-size scaling.The transition-window width scales as L^-1/ν, and the observed slope follows L^3/4 even for small systems.
- Finite-size scaling: R_L(η_c) − R_∞ scales as L^-2, attributed to the leading irrelevant renormalization exponent under periodic boundary conditions.The L^-2 correction is less severe than the L^-1 behavior stated for open boundaries.
- Threshold extrapolation: Combining the finite-size corrections gives η_L − η_c ∼ L^-11/4, so η_c is estimated by extrapolating η_L against L^-11/4.The extrapolated values are reported in Table I; error bars are obtained from fluctuations in R_L and weighted regression across system sizes.
IV. CONCLUSIONS
The union-find approach extends to continuum percolation, enabling highly accurate threshold estimates with essentially linear runtime in the number of critical objects. The results confirm conformal field theory predictions for finite-size scaling and wrapping probabilities.
- The union-find approach applies to continuous percolation and runs in essentially linear time as a function of the number of objects at criticality.It yields new estimates of ηc for multiple continuum models that are several orders of magnitude more accurate than previous results.
- The study obtains new estimates of ηc for a variety of continuum percolation models with substantially improved accuracy.
- The continuum models confirm conformal field theory predictions for the finite-size scaling exponent ν.
- The probabilities of different wrapping-cluster types at ηc on periodic boundary conditions also agree with conformal field theory predictions.