pith. sign in

arxiv: 2605.21921 · v1 · pith:UK3YSNRUnew · submitted 2026-05-21 · 💻 cs.DM · math.CO

On weighted partial triangulations of convex polygons

Antonio Blanca , Alexandre Stauffer , Izabella Stuhl This is my paper

Pith reviewed 2026-05-22 02:46 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords partial triangulationsconvex polygonsweighted samplingexact samplingrandomized algorithmscombinatorial enumerationgeometric partitions
0
0 comments X

The pith

A randomized algorithm exactly samples weighted partial triangulations of convex polygons in expected time O((n√λ + 1) log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a direct randomized procedure that generates an exact sample from the distribution over partial triangulations of a convex n-gon, where each partial triangulation σ is chosen with probability proportional to λ raised to the number of diagonals it contains. This model unifies several classical objects including full triangulations and Catalan structures under a single exponential weighting. Earlier methods depended on Markov chains whose mixing times were not always tight, while the new approach bypasses chains entirely to achieve near-optimal expected running time. If the claim holds, researchers gain a practical tool for generating exact instances of these weighted geometric partitions at scale.

Core claim

The authors present a randomized algorithm that produces an exact sample from the target distribution π_λ, defined by π_λ(σ) ∝ λ^{|σ|} for partial triangulations σ of a convex n-gon, and runs in expected time O((n √λ + 1) log n) for all sufficiently large n. The procedure is direct rather than Markov-chain based and applies uniformly for any fixed λ > 0.

What carries the argument

A direct recursive sampling procedure that selects diagonals according to their weighted contributions and decomposes the polygon into independent subproblems.

If this is right

  • The method supplies a nearly optimal sampler for the entire family of weighted partial triangulations.
  • It supplies an alternative to Markov-chain techniques whose mixing times may be suboptimal for the same objects.
  • The same direct approach extends in principle to the broader class of weighted geometric partition problems that includes lattice triangulations and dyadic tilings.
  • When λ equals one the sampler specializes to uniform generation over partial triangulations, recovering classical Catalan-related counts as a special case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar direct sampling techniques might be developed for weighted triangulations of point sets in the plane rather than convex polygons alone.
  • The running-time dependence on √λ suggests a natural scaling limit when λ grows with n that could be explored numerically.
  • Because the sampler is exact, it can serve as a building block for Monte Carlo estimation of other statistics on the same space without bias from approximate mixing.

Load-bearing premise

The procedure assumes a standard convex n-gon together with the exponential weighting by number of diagonals and that n is large enough for the time bound to apply.

What would settle it

Running the algorithm on a sequence of large n and fixed λ values and checking that the output frequencies match the exact weights λ^k / Z within statistical error would falsify the exactness claim if the match fails.

Figures

Figures reproduced from arXiv: 2605.21921 by Alexandre Stauffer, Antonio Blanca, Izabella Stuhl.

Figure 1
Figure 1. Figure 1: Examples of geometric partitions. (a) A full triangulation of a regular octagon. (b)-(c) Two partial triangulations of the same octagon. (d) A dyadic tiling of the unit square of size n = 16. (e) A lattice triangulation of a 4 × 5 rectangle. studied a Markov chain for sampling from distributions over lattice triangulations in which a triangulation τ has weight λ |τ| , with |τ | denoting the total edge leng… view at source ↗
Figure 2
Figure 2. Figure 2: (a): Construction of the string s =“(0)()()” in Υ3,1 from a partial triangulation in Ω4,3: s = (s(t0)0s(t1))s(t2) where s(t0) = s(t1) = ∅ and s(t2) =“()()”. (b) Construction of the string s =“(()0(00))” in Υ3,3 from a partial triangulation in Ω6,3: s = (s(t0)0s(t1))s(t2) where s(t0) =“()”, s(t1) =“(00)”, and s(t2) = ∅. Finally, note that Rout is a geometric random variable with support {1, 2, . . . }. When… view at source ↗
Figure 3
Figure 3. Figure 3: Two examples illustrating the construction of a partial triangulation from a string: (a)-(b) correspond [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
read the original abstract

We study the problem of sampling weighted partial triangulations of a convex polygon. We consider the distribution where each partial triangulation $\sigma$ is chosen with probability proportional to $\lambda^{|\sigma|}$, where $\lambda>0$ is a model parameter and $|\sigma|$ denotes the number of diagonals in $\sigma$. This model belongs to a broad class of weighted geometric partition problems that include lattice triangulations and dyadic tilings, and is closely related to several classical combinatorial structures, including the full triangulations of a convex polygon and the associated Catalan structures. While prior work has largely focused on Markov chain approaches, often only providing suboptimal mixing time bounds, we provide a direct efficient method for exact sampling. Our main result is a randomized algorithm that outputs an exact sample from the target distribution in expected time $O\big((n\sqrt{\lambda}+1)\log n\big)$ for all sufficiently large $n$. This provides a nearly optimal sampling algorithm for weighted partial triangulations, offering a compelling alternative to Markov chain-based techniques.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies exact sampling from the distribution over partial triangulations of a convex n-gon in which each partial triangulation σ is chosen with probability proportional to λ^|σ|. It presents a recursive randomized algorithm that decomposes the polygon by sampling a weighted non-crossing set of diagonals from a base edge and recurses on the resulting sub-polygons, claiming an expected running time of O((n√λ + 1) log n) for all sufficiently large n.

Significance. If the claimed runtime holds, the result supplies a direct exact sampler whose complexity is nearly linear in n and only square-root in the weight parameter λ. This improves on existing Markov-chain methods for the same family of weighted geometric partitions and Catalan-like structures, and the proof technique (generating-function recurrence plus tail bounds on sub-polygon sizes) is self-contained and parameter-free once λ is fixed.

minor comments (3)
  1. [Abstract and Theorem 1] The phrase “for all sufficiently large n” appears in the abstract and Theorem 1; please state explicitly whether the hidden constant depends on λ or is uniform in λ, and give a concrete lower bound on n if one exists.
  2. [Section 3.2] In the recurrence for the expected number of recursive calls (around Eq. (7)), the tail bound on the size of the largest sub-polygon is invoked; a short appendix deriving the precise constant in the exponential tail would help readers verify the √λ factor.
  3. [Section 2] Notation for the generating function T_n(x) is introduced without a displayed definition; adding the explicit recurrence T_n(x) = … would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, accurate summary of the main result, and recommendation for minor revision. We will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper derives an exact sampling algorithm via recursive decomposition of the convex n-gon, selecting a weighted non-crossing diagonal set from a base edge and recursing on sub-polygons. The expected-time recurrence is solved using the standard generating-function relation for the weighted partial triangulations together with elementary tail bounds on sub-polygon sizes. No step reduces a claimed prediction to a fitted parameter by construction, invokes a self-citation as the sole justification for a uniqueness or ansatz claim, or renames an input quantity as an output. The central result therefore rests on independent combinatorial recurrences and standard probabilistic bounds rather than on any self-referential definition or load-bearing self-reference.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The algorithm depends on the standard definition of partial triangulations of convex polygons and the exponential weighting by number of diagonals; lambda is an input parameter rather than a fitted constant.

free parameters (1)
  • lambda
    Positive real model parameter that controls the relative weight of configurations with more diagonals.
axioms (1)
  • domain assumption Convex polygons admit partial triangulations consisting of non-crossing diagonals.
    Standard fact from combinatorial geometry invoked to define the state space.

pith-pipeline@v0.9.0 · 5703 in / 1172 out tokens · 43027 ms · 2026-05-22T02:46:28.776080+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    Proceedings of the London Mathematical Society , volume=

    On the partitions of a polygon , author=. Proceedings of the London Mathematical Society , volume=. 1890 , publisher=

    work page

  2. [2]

    Stanley, Richard P. , year=. Catalan Numbers , publisher=

    work page

  3. [3]

    R. Un proc. RAIRO. Informatique th. 1985 , publisher=

    work page 1985

  4. [4]

    Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Phase Transitions in Random Dyadic Tilings and Rectangular Dissections , author=. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2014 , organization=

    work page 2014

  5. [5]

    Proceedings of RANDOM , pages=

    Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings , author=. Proceedings of RANDOM , pages=

    work page

  6. [6]

    Transactions of the American Mathematical Society , volume=

    The phase transition for dyadic tilings , author=. Transactions of the American Mathematical Society , volume=

    work page

  7. [7]

    Discrete mathematics , volume=

    Counting dyadic equipartitions of the unit square , author=. Discrete mathematics , volume=. 2002 , publisher=

    work page 2002

  8. [8]

    Proceedings of the Forty-fifth annual ACM Symposium on Theory of Computing (STOC) , pages=

    Random lattice triangulations: structure and algorithms , author=. Proceedings of the Forty-fifth annual ACM Symposium on Theory of Computing (STOC) , pages=

    work page

  9. [9]

    Stauffer, Alexandre , journal=. A. 2017 , publisher=

    work page 2017

  10. [10]

    Electronic Journal of Probability , number =

    Pietro Caputo and Fabio Martinelli and Alistair Sinclair and Alexandre Stauffer , title =. Electronic Journal of Probability , number =. 2016 , doi =

    work page 2016

  11. [11]

    2010 , publisher=

    Triangulations: structures for algorithms and applications , author=. 2010 , publisher=

    work page 2010

  12. [12]

    Algebra i Analiz , volume=

    Real plane algebraic curves: Constructions with controlled topology , author=. Algebra i Analiz , volume=

    work page

  13. [13]

    Dais, D. I. , title =. Geometry of Toric Varieties , series =. 2002 , mrnumber =

    work page 2002

  14. [14]

    Discriminants, resultants, and multidimensional determinants , pages=

    A-discriminants , author=. Discriminants, resultants, and multidimensional determinants , pages=. 1994 , publisher=

    work page 1994

  15. [15]

    , author=

    On the mixing time of the triangulation walk and other Catalan structures. , author=. Randomization methods in algorithm design , volume=

    work page

  16. [16]

    50th International Colloquium on Automata, Languages, and Programming (ICALP) , pages=

    Improved Mixing for the Convex Polygon Triangulation Flip Walk , author=. 50th International Colloquium on Automata, Languages, and Programming (ICALP) , pages=

    work page

  17. [17]

    DIMACS Series in Disc

    On the mixing rate of the triangulation walk , author=. DIMACS Series in Disc. Math. and Theoret. Comput. Sci , volume=

    work page

  18. [18]

    Faster Mixing for Triangulations via Transport Flows

    Faster Mixing for Triangulations via Transport Flows , author=. arXiv preprint arXiv:2605.02067 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  19. [19]

    Communications of the ACM , volume=

    Programming pearls: a sample of brilliance , author=. Communications of the ACM , volume=. 1987 , publisher=

    work page 1987